Binary Search in a sorted array-CodePudding

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!

CodePudding user response：

The formula for worst case is floor(log(n) 1)

In other words, you add one and round down. See https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance

But in my textbook, it says an array where n=10000, takes a max of 13 steps.

Your textbook is wrong. Binary search on an array with 10000 elements can take upto 14 steps, just as you would expect.

At each step, the array size would decrease by a factor of 2. so the steps would be 10000, 5000, 2500, 1250, 625, 312, 156, 78, 39, 19, 9, 4, 2, 1. As you can see, that's 14 steps.

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

You are correct, the book is wrong.

CodePudding user response：

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.

10 elements remain. Compare 50. Go right.
5 elements remain. Compare 500. Go right.
2 elements remain. Compare 1000. Go right.
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.