二分搜索算法和对数函数

cooolr 于 2021-02-23 发布

二分搜索算法

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