A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Ch. 2 Exercise 3

@jaywengrow

“What is the maximum number of steps it would take to perform a binary search on an array of size 100,000?”

“To solve this, we need to count how many times we halve 100,000 until we get down to 1. If we keep dividing 100,000 by 2, we see that it takes us 16 times until we get down to about 1.53.
This means a worst-case scenario would take about 16 times.”

Maximum number of steps should be 17, not 16. Perhaps dividing by 2 should be performed until the result is less than 1.

Excerpt From
A Common-Sense Guide to Data Structures and Algorithms, Second Edition
Jay Wengrow
https://itunes.apple.com/WebObjects/MZStore.woa/wa/viewBook?id=0
This material may be protected by copyright.