二分查找

查找函数：

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = int((low + high)/2)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

测试代码：

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

结果：

1
None

因为python索引是从0开始的，这里找到列表中的第二个元素索引为1。如果想让结果显示为2，只需要修改

        if guess == item:
            return mid+1

让程序在查找后位置加1即可。

问题：
1.1 假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请问最多需要几步才能找到？
答案： 7次，对128取log2
1.2 上面列表的长度翻倍后，最多需要几步？
答案：8次，翻倍就是乘以2，给7做一次加法，加1即可

代码和问题参考来源：《算法图解》