Python面试常用算法

import doctest

def binary_search(alist, item):
    """
    >>> alist=[1,3,4,7,11,18,29]
    >>> binary_search(alist,1)
    0
    >>> binary_search(alist,7)
    3
    >>> binary_search(alist,18)
    5
    >>> binary_search(alist,31)

    """

    binary_index = int(len(alist)/2)
    if alist == []:
        return None
    elif alist[binary_index] > item:
        return binary_search(alist[:binary_index], item)
    elif alist[binary_index] < item:
        result = binary_search(alist[binary_index + 1:], item)
        return  None if result is None else result + binary_index + 1
    elif alist[binary_index] == item:
        return binary_index

if __name__ == "__main__":
    doctest.testmod(verbose=True)