目录
假设你在玩一个猜数游戏,我会告诉你大了,正确,小了且范围为1~100。用普通方法(一个一个猜)最多需要猜100次,而二分查找却快得多。那么什么是二分查找呢?
二分查找是一种算法,输入必须为有序的元素列表。我先猜了50,小了,那么我就排除了一半,这就是二分查找!接下来可以重复二分查找直到找到正确值。
普通查找的速度为n(n为需要执行的操作数)
二分查找的速度为log n
def binary_search(list,item):
low=0
hight=len(list-1)#用于跟踪要查找的部分
while low<=hight:#只要范围没有缩小到只包含一个元素
mid=(low+high)/2#就检查中间元素
guess=list[mid]
if guess==item:#找到了
return mid
if guess>item:
hight=mid-1
else:
low=mid+1
return none
算法就是这样,但是测试用的list和item需要读者自己编写。