二分查找

binary_search.py

def binary_search(lst, num):
    if num not in lst:
        return None
    last = len(lst)
    first = 0
    while(last>first):
        mid = (last + first) / 2
        if lst[mid] == num:
            return mid
        elif lst[mid] > num:
            last = mid
        else:
            first = mid + 1
    return None


if __name__ == '__main__':
    assert binary_search([1,3,5,6,7,10,14,28,33], 5) == 2
    assert binary_search([1,3,5,6,7,10,14,28,33], 28) == 7
    assert binary_search([1,3,5], 3) == 1
    assert binary_search([1,3], 1) == 0
    assert binary_search([1], 1) == 0
    print('Well Done!')