体会下经典的二分查找算法。二分操作算法只能由于有序数组，时间复杂度是O(lgN)。在链表情况下，类似二分查找的数据结构是跳表，查找的时间复杂度是O(lgN)。

二分查找算法虽然简单，但在有序数组情况下，性能很好。

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search(list, key):
    lo = 0
    hi = len(list) - 1
    while lo <= hi:
        mid = lo + (hi-lo) // 2
        if list[mid] < key:
            lo = mid + 1
        elif list[mid] > key:
            hi = mid - 1
        else:
            return mid
    return -1