How many comparisons will binary search make in the worst case using this algorithm?

Question

Hi there below is the pseudo code for my binary search implementation:

Input: (A[0...n-1], K)
begin
   l ← 0; r ← n-1
   while l ≤ r do
      m ← floor((l+r)/2)
      if K > A[m] then l ← m+1
      else if K < A[m] then r ← m-1 else return m
      end if 
   end while
   return -1 // key not found
end

I was just wondering how to calculate the number of comparisons this implementation would make in the worst case for a sorted array of size n?

Would the number of comparisons = lg n + 1? or something different?

Answer 1

The worst-case in this case is, if the element K is not present in A and smaller than all elements in A. Then we have two comparisons in each step: K > A[m] and K < A[m].

For in each step the array is being cut into two parts, each of the size (n-1)/2, we have a maximum of log_2(n-1) steps.

This leads to a total of 2*log_2(n-1) comparisons, which asymptotically indeed equals to O(log(n)).