Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence is sorted, we can check the midpoint of the sequence against and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is .

Pseudo-code for ITERATIVE-BINARY_SEARCH(A, v)

1
2
3
4
5
6
7
8
9
10
11
low = A[1]
high = A[A.length]
while low ≤ high
    mid = (low + high) / 2
    if v == A[mid]
        return mid
    elseif v > A[mid]
        low = mid + 1
    else
        high = mid - 1
return NIL

Pseudo-code for RECURSIVE-BINARY-SEARCH(A, v, low, high)

1
2
3
4
5
6
7
8
9
if low > high
   return NIL
mid = (low + high) / 2
if v == A[mid]
    return mid
elseif v > A[mid]
    RECURSIVE-BINARY-SEARCH(A, v, mid + 1, high)
else
    RECURSIVE-BINARY-SEARCH(A, v, low, mid - 1)

Intuitively, in worst case, i.e. when is not at all present in , we need to binary search over the whole array to return NIL. So in worst-case, we need to repeatedly divide the array by 2. So the running time is nothing but how many times the input size can be divided by 2, i.e. .

And using recurrence formula, we can say running time .

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.