原理
二分法查找的原理非常直观和易于理解：
假设有一个已经排序好的列表，在其中查找某个元素，如果查找到，就返回该元素的索引index值，如果没有查找到，则返回None.
这个算法有两个版本，递归和非递归，递归的版本比较容易理解。
要点
需要注意的是，在判断是否对整个列表遍历完的时候，需要判断现在搜索的列表首尾元素索引值是否有效，如果首元素索引值已经超过尾元素的索引值，则整个遍历已经结束，只是没有找到，应该直接返回None.
Python代码实现
下面的代码在Python 3上测试通过
递归版本：
def bin_search_recursively(l, first, last, n):
'''Binary search n in list l which has been sorted already, returns
the index if found, else returns None.'''
if first > last:
return None
mid = (first + last) // 2 # Use / 2 if you're using Python 2
if l[mid] > n:
return bin_search_recursively(l, first, mid - 1, n)
elif l[mid] < n:
return bin_search_recursively(l, mid + 1, last, n)
else:
return mid
if __name__ == '__main__':
sorted_num_list = list(range(1, 11))
first = 0
last = len(sorted_num_list) - 1
n1 = 12
n2 = 6
print(bin_search_recursively(sorted_num_list, first, last, n1))
print(bin_search_recursively(sorted_num_list, first, last, n2))
代码输出：
None
5
非递归版本：
def bin_search_nonrecursively(l, first, last, n):
'''Binary search n in list l which has been sorted already, returns
the index if found, else returns None.'''
while first <= last:
mid = (first + last) // 2 # Use / 2 if you're using Python 2
if l[mid] > n:
last = mid - 1
elif l[mid] < n:
first = mid + 1
else:
return mid
return None
if __name__ == '__main__':
sorted_num_list = list(range(1, 11))
first = 0
last = len(sorted_num_list) - 1
n1 = 12
n2 = 6
print(bin_search_nonrecursively(sorted_num_list, first, last, n1))
print(bin_search_nonrecursively(sorted_num_list, first, last, n2))
代码输出：
None
5
