引言

二分查找算法最典型的应用莫过于猜数，假如你的朋友要你猜中他心里想的一个数字，这个数字在0-99之间，你每猜一次，他都会告诉你是否猜中亦或是数字偏大或偏小。那么你会怎样猜测呢？

从0猜到99，猜100次
99猜到0呢，还是100次

666

当然最省事的办法就是：先猜50，如果偏大；再猜25，还是偏大；再猜12，还是偏大；再猜6，还是偏大；再猜3，还是偏大；再猜1，还是偏大；那么就只能是0了！这时你可能会说要是一开始猜0早就结束了，不过你就确定你的好友不会想个99吗！

算法分析

从上面我们可以看出，采用二分法猜测，在最坏的情况我们会猜测次即最多7次，所以算法复杂度为O()；而我们盲目猜测时最坏的结果回达到100次，所以算法复杂度为O(n)；当然了你也许会说100次我还承受的了，那么我们来看看这个数1125899906842620，如果从0开始，估计你整个青春都浪费了，而采用二分法呢?我们只需要50次，因为这个数等于2^50方。

Python代码

# -*- coding : utf-8 -*-


def binary_search(array, item):
    low = 0   # 数组下标以0开始计算
    high = len(array) - 1  # 计算数组高位位置

while low <= high:  # 只要范围没有缩小到只剩一个元素
    mid = int((low + high) / 2)  # 二分法精髓，从最中间开始查找;int 向下取整
    guess = array[mid]
    if guess == item:
        return mid
    if guess > item:
        high = mid - 1
    else:
        low = mid + 1
return "Not Found"


if __name__ == "__main__":
    test_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 21]
    print("寻找1的位置：\n", binary_search(test_array, 1))
    print("寻找14的位置：\n", binary_search(test_array, 14))