二分查找必须是有序集
#!/usr/bin/env python3
def binary_search(array, item):
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
guess = array[mid]
if guess == item:
return mid
elif guess > item: # 猜大了
high = mid - 1
else: # 猜小了
low = mid + 1
return None
l1 = [1, 3, 6, 11, 24, 58]
l2 = [2, 5, 8, 90]
n1 = binary_search(l1, 11)
n2 = binary_search(l2, 2)
print(n1)
print(n2)
二分查找每次可排除掉一半的元素，最坏的情况下要查找 log(n) 次
算法运行时间是 O(log(n)) 对数级的
大 O 表示法表示的是算法运行时间的上限，表示随着输入规模的增加二分查找运行时间的增长率是对数级的, 对数级的算法增长率较慢
