How is maximum key compare in binary search (1+log(n)) not log(n)?

Question

I was re going through a more versatile explanation of BS. Which has a preposition that maximum number of key compare in a binary search is (1+log(n)). I tried to form an intuition as to how is that possible. I understand the ruining time of BS is (log(n)). Also i speculate that the worse time/maximum key lookups will happen in scenario when we search for a element which is not present in the array. But each time i go over a hypothetical array doing a BS i end up with (log(n)) compares/steps never more than that. Here is the code which was used to form that preposition.

public static int binarySearch(int[] a, int key){
     int lo = 0, hi = a.length-1;
     while (lo <= hi){
         int mid = lo + (hi - lo) / 2;

         if (key < a[mid]) 
            hi = mid - 1;
         else if (key > a[mid]) 
            lo = mid + 1;
         else 
            return mid;
     }
     return -1;
 }

Probably my speculation is wrong or i am missing some point. If you could explain how maximum possible key compares would be (1+log(n)) it would be great thanks.

Answer 1

Don't forget that even when you have only 1 element, you still have to guess it, because it is possible that the target is not in the array. So we need to add on the +1 for the last guess when we are down to the final remaining element.

It may be clearer if you think about when n=1. We still need 1 guess, but log_2(1) = 0. So we need to add a +1 to fix up the formula.

When n is not a power of 2, we can just go up to the next higher power of 2. For an array whose length is 1000, the next higher power of 2 is 1024, which is 10. Therefore, for a 1000-element array, binary search would require at most 11 (10 + 1) guesses.

Why?

In the worst case, binary search would need 10 steps to separate the remaining numbers and 1 final step to check whether the only one number left is what you want, or it's not in the array.

Answer 2

Here's a different way to think about what you're doing. Rather than thinking of binary search as searching over the elements of the array, think of binary search as searching over the separators between the elements in the array. Specifically, imagine numbering the array like this:

   +-----+-----+-----+-----+-----+
   |  0  |  1  |  2  | ... | n-1 |
   +-----+-----+-----+-----+-----+

Now, number the separators:

   +-----+-----+-----+-----+-----+
   |  0  |  1  |  2  | ... | n-1 |
   +-----+-----+-----+-----+-----+
   0     1     2     3 .. n-1    n

Notice that there are n+1 total separators, one before each element and one after the very last element.

Whenever you do a binary search, you're probing the index of the middle separator (do you see why?) and throwing half of the separators away. You can only throw half of a collection of k items away log₂ k times before you're down to a single remaining element. This means that the number of probes needed will be ⌈log₂ (n+1)⌉, and it happens to be the case that

log₂ n < ⌈log₂ (n+1)⌉ ≤ log₂ n + 1,

so the "1 + log n" bit ends up arising more from "throw away half the separators" than from other sources.

Hope this helps!

Answer 3

Imagine an array of size 8.

l=0, h = 7, mid =  0 + (7-0)/2 = 3   go right
l=4, h = 7, mid =  4 + (7-4)/2 = 5   go right
l=6, h = 7, mid =  6 + (7-6)/2 = 6   go right
l=7, h = 7, mid =  7 + (7-7)/2 = 7   go left  
l=7, h=6 ====> terminates

Total comparisons = 1 + Log 8 = 4

EDIT1: Imagine this array and use a pen and paper and trace out the above steps. Search for value 13.

index:      0  1  2  3  4  5  6   7   
            ------------------------------
element:    1  3  5  6  7  9  11  15