Binary Search

November 16, 2018

Binary search is used to locate an element in an array efficiently than the linear search. To use a binary search, the array must be sorted in non-decreasing order. If T[1…n] is the sorted array, then the binary search returns an index i at which the element(say x) is found. If the element is not in the array then, it returns a possible index where the element might be inserted. Here, we wish to find the index i such that 1 < i < n + 1 and T[i - 1] < x < T[i].

At first, let’s see how do we locate an element in an array using linear or sequential approach.

LINEAR-SEARCH (T[1…n], x)

for i = 1 to n
    if T[i] > x
        return i
return n + 1

From the above algorithm, we can see clearly that the algorithm takes the time in θ(n) in the worst case where n is the number of elements. Now, let’s see how binary search algorithm will improve this running time. Basically, a binary search algorithm works like this. First, we compare the element x with the middle element of the array. As the array is sorted, if x is greater than the middle element of the array, then we do not have to search x in the left portion of the array. Otherwise, we search for x in the left portion of the array and do not have to search in the right portion of the array. The figure below will illustrate this.

Suppose we are searching for the number 9 in the sorted array:

Loading — Binary search for x = 12 in T[1...11] [Source: Fundamental of Algorithmics]

In the pseudocode below, we first check whether x lies within the range T[1] to T[n]. If it does not, we will return n + 1 and avoid the unnecessary recursive calls.

BINARY-SEARCH(T[1…n], x)

if n = 0 or x > T[n]
    return n + 1
else
    return BINARY-RECURSIVE(T[1…n], x)

BINARY-RECURSIVE(T[i…j], x)

if i == j
    return i
k = (i + j) / 2
if x < T[k]
    return BINARY-RECURSIVE(T[1…k], x)
else
    return BINARY-RECURSIVE(T[k + 1 … n], x)

Analysis: Let, t(n) be the time required for a call on BINARY-RECURSIVE(T[i…j], x) where n = j – i + 1 is the number of elements. The time required for BINARY-SEARCH(T[1..n], x) is also t(n) with a small additive constant for conditional checking. For the recursive call we can use t(n) = t(n/2) + g(n) when n is even and g(n) = θ(1) = θ(n⁰) = θ(n^log₂1) because the algorithm takes a constant amount of time besides recursive calls. Even when n is odd, master theorem can be used and by using master theorem, t(n) = θ(n^log₂1 log n) = θ(log n). So, binary search has logarithmic time complexity.

I think it is worth mentioning that the above algorithm can be implemented iteratively rather than recursively. The running time will be same in both cases. The only difference is that recursion needs some additional spaces because of function calls.

Reference:
Fundamentals of Algorithmics