假设我们要从一个电话簿中查找一个以L打头的人，可以从头开始翻页，直接进入L打头的部分。但我们可能不这么做，我们可能从中间开始，因为我们知道以L打头的名字在电话簿的中间；再假设我们从字典中查找一个以字母O打头的单词，我们也将从中间开始查找。 如果现在假设你要登录Facebook，当你这样做的时候，Facebook必须核实你的是否具有该网站的注册账户信息，因此他会从数据库中查找你的用户名，假设你的用户名为sunyboy，Facebook可以以A打头开始查找，更合乎逻辑的做法是从中间开始查找。
这是一个查找的问题，在上述所有请情况下，都可以使用同一种算法来解决问题，这种算法是二分查找。
概念
二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置，否则返回null。
基本原理
通过一个实例来说明二分查找的原理；
你随便想一个1~100的数字，我的目标是以最少的次数猜到该数字。我每次猜测之后，你会说小了、大了或对了。
假设我从1开始猜测，这样一个一个数字猜测，每次猜测都只能排除一个数字。如果你想的数字是99，我得猜测99次才能猜到！这是简单查找，更准确的说法就是傻找；
最佳的方法是从这个数字1~100之间取中间数，这样就可以排除一半的数字！我知道1~50都小了，我会去猜测75，你说数字大了，我会去猜测63，你说大了，我会猜测57，这就猜对了；这种查找方法会在7次内猜测出答案，这个7又是如何得来的呢？ 一般而言，对于包含n个元素的列表，用而二分查找最多需要log2n（对数：例：2^3=8 <-> log28=3 ）步，而简答查找最多需要n步；
代码示例
__Author__ = "ZhiChao Ma"
#versions:Python3.5.2
#使用二分查找法快速从一个数组中查找一个指定元素，并返回该元素的索引值
def binary_search(list, item):
#low和high用于跟踪要在其中查找的列表部分
low = 0
high = len(list)-1
while low <= high: #只要范围没有缩小到只包含一个元素
#如果(low + high)不是偶数，python自动向下取整，这里来检查中间元素
mid = (low + high)
guess = list[mid]
if guess == item: #找到了元素
return mid
if guess > item: #猜的数字大了
high = mid -1
else: #猜的数字小了
low = mid + 1
return None #没有指定元素
my_list1 = ['zhangsan', 'lisi', 'wangwu',]
my_list2 = list(range(10000))
print(binary_search(my_list1, 'lisi'))
print(binary_search(my_list2, 5002))
print(binary_search(my_list2, -110))
输出结果：
1
5002
None