软件环境:Python 3.7.0b4
def binary_search(list, item):
# low 和 high 用于跟踪要在其中查找的部分
low = 0
high = len(list) - 1
# 只要范围没有缩小到只有一个元素,就继续循环
while low <= high:
# 检查中间的元素
mid = (low + high) / 2
guess = list[mid]
# 如果猜的数是对了,返回结果
if guess == item:
return mid
# 如果猜的数大了,上限减1
if guess > item:
high = mid - 1
# 如果猜的数小了,下限加1
else:
low = mid + 1
# 如果没有这个元素,返回None
return None
my_list = [1, 3, 5, 7, 9] ##测试数据
1.1:128->64->32->16->8->4->2->1,所以最多需要7步。
1.2:翻倍后顶多会增加一步,所以是8步。
1.3:可以根据字母姓氏进行二分查找,所以是O(log n)。
1.4:属于简单查找,所以是O(n)。
1.5:属于简单查找,所以是O(n)。
1.6:O(n)。