bin_search.py

# Binary search solves the problem [of searching within a pre-sorted array] by
# keeping track of a range within the array in which T [i.e. the sought value]
# must be if it is anywhere in the array.  Initially, the range is the entire
# array.  The range is shrunk by comparing its middle element to T and
# discarding half the range.  The process continues until T is discovered in the
# array, or until the range in which it must lie is known to be empty.  In an
# N-element table, the search uses roughly log(2) N comparisons.

def bin_search(A, T):
    """
    A binary search in python.

    >>> from bin_search import bin_search
    >>> bin_search(range(4),3)
    3
    >>> bin_search(range(50),7)
    7
    >>> bin_search(range(50),26)
    26
    >>> bin_search(range(50),99)
    >>> bin_search(range(50),-1)
    >>> bin_search(range(3),1)
    1
    >>> bin_search([],1)
    >>> bin_search(range(25,50),25)
    0
    >>> bin_search(range(25,50),49)
    24
    >>> bin_search([1],1)
    0
    >>> bin_search([1],22)
    >>> bin_search(range(5),4)
    4
    >>> bin_search([0,1,4,4,5,6],4)
    3

    """
    low = 0;
    high = len(A)

    while (low <= high):
        mid = low + (high-low)/2
        if mid == len(A):
            return None

        mid_val = A[mid]

        if T == mid_val:
            return mid
        elif T < mid_val:
            high = mid-1
        else:
            low = mid+1

    return None

if __name__ == '__main__':
    import doctest
    doctest.testmod()