定义:
二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2...
例如需要查找有序数组arr里面的某个关键字key的位置,那么首先确认arr的中位数或者中点center,下面分为三种情况:
假如arr[center]>key,说明key在arr中心左边范围;
假如arr[center]<key,说明key在arr中心右边范围;
假如arr[center]=key,说明key在arr中心。
规定:
范围每次缩小一半,写个while的死循环知道找到为止。
二分法查找非常快且非常常用,但是唯一要求是要求数组是有序的。
代码:
list = [1,2,3,4,7,10,50,60,100]
min = 0
max = len(list) - 1
count = 80
while True:
print("找到了")
center = int((min+max)/2)
if list[center] > count:
max = center - 1
elif list[center] < count:
min = center + 1
elif list[center] == count:
print("索引是%d"%center)
break