二分查找

假设要在电话簿中找一个名字以K打头的人，（现在谁还用电话簿！）可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。
又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。
这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问题，这种算法就是二分查找。

仅当列表是有序的时候，二分查找才管用。

电话簿中的名字是按字母顺序排列的，因此可以使用二分查找来查找名字。如果名字不是按顺序排列的，结果将如何呢？

low = 0
high = len(list) - 1
mid = (low + high) / 2  
# 取中间元素
guess = list[mid]
# 自动将mid向下取整
# 根据数字调整mid
if guess < item:  
    low = mid + 1

def binary_search(list, item):
    low = 0 
    # 数组长度，数组长度从1计数，而索引从0计数
    high = len(list) - 1  
    while low <= high: 
        mid = (low +high) / 2
        guess = list[mid]
        if guess == item:
            return mid
        # 猜的数字大了，减小mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1 
    # while循环结束没有找到指定的数字
    return None

一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。
回到前面的二分查找。使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。
最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
二分查找则不同。如果列表包含100个元素，最多要猜7次；
如果列表包含40亿个数字，最多需猜32次。
厉害吧？二分查找的运行时间为对数时间（或log时间）。
随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。因此，随着列表的增长，二分查找的速度比简单查找快得多。