Binary Search in a sorted array

Question

I've just started learning some basic algorithms, but there’s something about the binary search algorithm that’s been confusing me.

From what I understand the max time complexity of a binary search is O(log(n)) where log is base 2.

However, when using the formula on values of N that is not a power of 2, you get a non-integer value.

What I am confused about is if you end up with, let’s say 3.3, is that a maximum of 3 steps or 4 steps.

You get the value 3.3 when using an array where n = 10. That being said, I manually counted the number of steps and I got 4, so I’m assuming you round up.

But in my textbook, it says an array where n=10000, takes a max of 13 steps. When putting that in the log formula above we get 13.2, which means in this case we rounded down.

I’ve tried a binary search with arrays of different sizes and I get instances where I must round down to get the textbook answer and instances when I must round up.

What I am unsure of is when to round up or down, or if I making another mistake entirely.

If anyone is to give me an example, could you please use an array of size 100000. Since in the book it says a maximum of 16 times, but when I manually half 100000 until I get 1 I get 17 times.

Thanks in advance!

Answer 1

Let's use the small example of 10, learn to walk before we run. Say the array is [2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000] and we're searching for 3000.

1. 10 elements remain. Compare 50. Go right.
2. 5 elements remain. Compare 500. Go right.
3. 2 elements remain. Compare 1000. Go right.
4. 1 element remains. Compare 2000. Go right (or decide "not found").

That is 4 comparisons. So yes, you round up, because you can't do a "partial step" for free, sometimes you get lucky and have fewer steps though, as in the above example if you searched for 1 it would only take 3 comparisons (50, 5, 2) assuming rounding the index toward the left for even-length groups.