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

The formula for worst case is

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.