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

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

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) = 0C(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) = 0C(1) = 2C(2) = 3C(3) = C(4) = 4C(5) = C(6) = 5C(7) = C(8) = C(9) = C(10) = 6C(11) = ... = C(14) = 7C(15) = ... = C(22) = 8C(23) = ... = C(30) = 9

So by induction we prove

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), andC(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.

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.