Binary Search

The aim is to find the index of an element in a sorted array. The input must be an array sorted in ascending order.

We search the sorted array by repeatedly dividing the search interval in half. We begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, we narrow the interval to the lower half. Otherwise, we narrow it to the upper half. We repeatedly check until the value is found or the interval is empty.

Intuitive Example: Searching for the name of a person in a list of names sorted in alphabetical order.

Binary Search can be solved in both a recursive and iterative manner:

Python code for recursive Binary Search:

def bin_search_recursive(a, k, l, h):
    mid = (l+h)//2
    if k==a[mid]:
        return mid
    elif k<a[mid]:
        return bin_search_recursive(a, k, l, mid-1)
    else:
        return bin_search_recursive(a, k, mid+1, h)

def bin_search_call(a, k):
    return bin_search_recursive(a, k, 0, len(a))

a = [int(x) for x in input("Enter array a: ").strip().split()]
k = int(input("Enter key k: "))
try:
    print("%d found at index %d" %(k, bin_search_call(a, k)))
except:
    print("Element not found!")

Python code for iterative Binary Search:

def bin_search_iterative(a, k):
    l = 0
    h = len(a) - 1

    while l<=h:
        mid = (l+h)//2
        if k==a[mid]:
            return mid
        elif k<a[mid]:
            h = mid-1
        else:
            l = mid+1

a = [int(x) for x in input("Enter array a: ").strip().split()]
k = int(input("Enter key k: "))
try:
    print("%d found at index %d" %(k, bin_search_iterative(a, k)))
except:
    print("Element not found!")

Time complexity: O(lg n)