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?

Solution 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)).

Solution 2

A very minor correction to hielsnoppe's answer:

In an n-element array (n > 0), the element to compare is at index m = floor((n-1)/2). So there are three possibilities

1. A[m] < K, then after one comparison, the search continues in an n-1-m = ceiling((n-1)/2)-element array.
2. A[m] > K, then after two comparisons, the search continues in an m-element array.
3. A[m] == K, then we're done after two comparisons.

So if we denote the maximal (worst-case) number of comparisons for a search in an n-element array by C(n), we have

C(0) = 0
C(n) = max { 1 + C(ceiling((n-1)/2), 2 + C(floor((n-1)/2) }, n > 0

For odd n = 2k+1, the floor and ceiling are identical, so the maximum is evidently the latter,

C(2k+1) = 2 + C(k)

and for even n = 2k, we find

C(2k) = max { 1 + C(k), 2 + C(k-1) }.

For n = 2, that resolves to C(2) = 1 + C(1) = 1 + 2 = 3, for all larger even n, the maximum is 2 + C(k-1), since for n >= 1 we have C(n) <= C(n+1) <= C(n) + 1.

Evaluating the recursion for the first few n, we find

C(0) = 0
C(1) = 2
C(2) = 3
C(3) = C(4) = 4
C(5) = C(6) = 5
C(7) = C(8) = C(9) = C(10) = 6
C(11) = ... = C(14) = 7
C(15) = ... = C(22) = 8
C(23) = ... = C(30) = 9

So by induction we prove

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), and
C(n) = 2k+1, if 2^k + 2^(k-1) <= n+1 < 2^(k+1)

or

C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))).

This is an exact upper bound.

Solution 3

According to the wikipedia page on binary search, the worst-case performance of this algorithm is O(lg n), which measures the asymptotical number of comparisons needed. The actual worst-case number of comparisons would be 2*lg(n-1), as has been pointed in @hielsnoppe's answer.

The pseudocode in the question represents the typical implementation of a binary search, so the expected performance complexities hold for an array (or vector) of size n:

• Best case performance: O(1)
• Average case performance: O(lg n)
• Worst case performance: O(lg n)

On closer inspection, there are two problems with the pseudocode in the question:

• The line: if K > A[m] then return l ← m+1 should read if K > A[m] then l ← m+1. You can't return yet
• The line: m ← floor((l+r)/2) might cause an overflow if the numbers are large enough when working with fixed-size integers. The correct syntax varies depending on the actual programming language you're using, but something along this will fix the problem: m ← (l + r) >>> 1, where >>> is the unsigned right shift operator. Read more about the problem in here.

Comments

[Pikesh Prasoon]

The worst case should be if all elements are the same! Thus the time complexity should be O(n)

[rohitt]

Can I say that for N sorted elements, there will be floor(log2(N+1)) comparisons in the worst case. By the worst case, I mean that the element is not in the list?