假期无聊,在家无网络,就看了看传说中的算法,一个字难
下面都是本人的愚见,如有不对请谅解:
二分查找的前提是有序其次是排除一半,比如1..100之间猜一个数值的大小,从50猜起,去掉一半,大了还是小了,这样会快很多
接下来是我写的python示例
运行结果
6
None
可复制如下:
def binary_search(list1,item):
low = 0
high = len(list1) - 1
while low <= high:
mid = ( low + high ) / 2
guess = list1[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [1,5,8,11,19,22,31,35,40,45,48,49,50]
print binary_search( my_list,31)
print binary_search( my_list,2 )