二分查找也叫做折半查找。二分查找的条件：①是一个有序序列 ②是一个顺序表。
比如有序的列表：[1,2,3,5,6,7,8,9]
二分查找的复杂度：
最优复杂度：O(1)
最坏复杂度：O(logn)
算法思想：
给定一个序列，查找序列中是否有元素a，查找的方法是：将序列折半，找到中间位置的数值mid，将该数值和a进行比较，比a大，则在左边的序列中找a是否存在，方法还是折半查找，如果mid比a小，那么在中间值右边中的序列中找a是否存在，方法也还是折半查找。可以看到上面有部分重复的功能，就是折半查找，这块可以使用递归，也可以不使用递归。下面会给出两个例子分别介绍这两种方法：
例1：递归实现：
def binary_find(alist,item):
n = len(alist)
#递归结束条件
if n == 0:
return False
mid = n//2
if alist[mid] == item:
return True
elif alist[mid] > item:
return binary_find(alist[:mid],item)
else:
return binary_find(alist[mid+1:],item)
l = [1,2,9,34,999]
re = binary_find(l,22)
print(re)
re = binary_find(l,999)
print(re)
运行结果：
False
True
例2：非递归实现
def binary_find2(alist,item):
n = len(alist)
start = 0
end = n-1
while start <= end: #这里要注意等于不能少
mid = (end + start)//2
if alist[mid] == item:
return True
elif alist[mid] > item:
end = mid - 1
else:
start = mid + 1
return False
l = [1,2,9,34,999]
re = binary_find2(l,22)
print(re)
re = binary_find2(l,999)
print(re)
运行结果：
False
True
复杂度分析：
可以看到上面的最优的复杂度就是正好中间的mid值就是我们要查找的值，复杂度为O(1)，最坏复杂度就是：logn
其实如果不用二分法查找，使用for循环也是可以的，但是如果数据很大，那么查找速度很慢，for循环查找的最优复杂度为O(1)，最坏复杂度为O(n)，而我们的二分法查找最坏复杂度是O(logn)，所以可以看到复杂度有所降低。