binary_search.py

# Binary Search Algorithm - requires the sequence to be already sorted.
# If the elements exists in the sequence, returns the index of the found 
# element, otherwise returns None.
# Time complexity - lgn
from __future__ import print_function


def binary_search(seq, key):
    imin = 0
    imax = len(seq)
    while imax > imin:
        midpoint = (imin + imax) // 2
        if key == seq[midpoint]:
            return midpoint
        if key > seq[midpoint]:
            imin = midpoint + 1
        else:
            imax = midpoint
    return None


def binary_search_recursive(seq, key, imin=0, imax=None):
    if imax is None:
        imax = len(seq)

    if imax < imin:
        return None

    midpoint = ((imax - imin) // 2) + imin
    if key == seq[midpoint]:
        return midpoint
    if key > seq[midpoint]:
        return binary_search_recursive(seq, key, midpoint+1, imax)
    else:
        return binary_search_recursive(seq, key, imin, midpoint-1)


if __name__ == '__main__':
    print(binary_search([0, 2, 3, 6, 9, 11, 12], 2))
    print(binary_search_recursive([0, 2, 3, 6, 9, 11, 12], 5))