【引言】早晨一女生背着一堆书出了图书馆，结果警报响了，大妈让女生看看是哪本书把警报弄响了，那女生把书倒出来，准备一本一本的测。大妈见状急了，把书分成两份，第一份过了一下，响了。又把这一份分成两份接着测，三回就找到了，大妈用鄙视的眼神看着女生，仿佛在说O(n)和O(logn)都分不清。
二分查找是一种用于 有序序列 的简单高效的查找元素的方式。
算法过程
二分查找的核心就是在于逐渐逼近（有点夹逼定理的感觉），从有序数组的两边，逐渐的向所要查找的元素周围逼近，最终锁定元素。
从7个数的数组中找到2的过程
二分查找每一次的查找都会减少当前锁定范围的一半，因此时间复杂度为：
二分查找时间复杂度
- 这样就使得如果我们要在一个含有 100 个数的有序序列中查找一个数，如果我们顺序查找，那么我们最多可能会查找 100 次；如果我们使用二分查找，我们最多需要 7 次就可以找到了。
- 如果我们要在一个包含 240000 个单词的字典中找到一个单词，如果我们顺序查找，那么我们最多可能会查找 240000 次才能找到；如果我们使用二分查找，我们最多需要 17 次就可以找到了。
算法实现
- 非递归二分查找
# 非递归二分查找算法
def binary_search(list, item):
low = 0
high = len(list) - 1
search_times = 0
while low <= high:
search_times += 1
mid = (low + high) // 2
guss = list[mid]
if guss == item:
return mid, search_times
if guss > item:
high = mid
else:
low = mid
return None
- 递归二分查找
# 递归二分查找算法
def recursion_binary_search(list, item, low, high, search_times=1):
mid = (low + high) // 2
guss = list[mid]
if low > high:
return None, search_times
if guss == item:
return mid, search_times
elif guss > item:
return recursion_binary_search(list, item, low, mid, search_times+1)
else:
return recursion_binary_search(list, item, mid, high, search_times+1)
return None
引言内容来自朋友圈，感谢我雷哥
