0x000f - Searching Algorithms – Part 2

Binary Search

The binary search algorithm, a variation of the Dichotomic search, finds the position of a specified “key” within a sorted list/array using the divide and conquer approach.

At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special indication is returned, saying that the key was not found.

Consider an example with 1-based array indexing. We have an array of sorted elements – 2, 6, 7, 34, 76, 123, 234, 567, 677 and 986 – and we are required to find the position of ‘123’. The steps involved while applying the binary search algorithm are:

Original illustration no longer available.

The search terminates with a result “found” when first, mid and last point to the same index, the index at which the desired key is found.

Since at every stage the number of items to be checked is halved, the time taken to find a particular element will be logarithmic in base 2. Thus, in most situations, such as ones involving sorted arrays/lists, a binary search will give results faster than a linear/sequential search.

The worst case time is O(log2 n), i.e. O(lg n), where lg implies log2, which occurs when the key to be found requires the maximum number of steps. So, for a large number of elements n, the running time of the binary search algorithm is much shorter than that of a linear search. The average case too is O(lg n) and the best case is O(1), when the desired key is at the first position checked.

The iterative implementation of this algorithm in Python is:

# Iterative Binary Search
def iter_bs(a, value) :
    low, high = 0, len(a)-1
    while low <= high:
        mid = (low + high)//2
        if value == a[mid]:
            return "The element %s was found at index %s" % (value, mid)
        if value < a[mid]:
            high = mid - 1
        else: low = mid + 1

    return "The element %s was not found." % value

The recursive version in Python is:

# Recursive Binary Search
def rec_bs(a, value, low, high) :
    if high < low:
        return "The element %s was not found." % value
    mid = low + (high - low)//2
    if a[mid] > value:
        return rec_bs(a, value, low, mid-1)
    elif a[mid] < value:
        return rec_bs(a, value, mid+1, high)
    return "The element %s was found at index %s." % (value, mid)