二分搜索算法
def Search(List, target):
global Count
print(Count, List, target)
Count += 1
index = int(len(List)/2)
if List[index] == target or List[0] == target or List[-1] == target:
return True
if len(List) <= 3:
return False
if target < List[index]:
return get(List[:index], target)
else:
return get(List[index:], target)
Count = 1
print(Search(range(8), 5))
二分搜索算法在搜索含有N个条目的列表时,最差情况下(找不到)最多要询问$log$2$N$个条目。(以2为底N的对数)
比如二分搜索含有为8个条目的列表时,最差情况下最多要询问条目数x为: 2**x=8 → x=3