《算法图解》第一章学习心得

二分法学习要点：仅当列表是有序的时候， 二分查找才管用。 如按英文字母表排序的电话簿。时间复杂度为log2（n）

二分法搜索的python3代码

def binary_search(list,item):
    low=0
    high=len(list)-1#low和high用于跟踪要在其中查找的列表位置
    while low<=high:
        mid=int((low+high)/2)#与书中代码不同，将数字转为int，列表索引才能用
        guess=list[mid]
        if guess==item:
            return guess
        if guess>item:
            high=mid-1#猜的数字大了,范围缩小到下半区
        else:
            low=mid+1#猜的数字小了,范围缩小到上半区
    return None#查无此人，返回None
           

测试样例：

my_list = [1, 3, 5, 7,9]
print(binary_search(my_list,9))
print(binary_search(my_list,8))
           

输出：

9
None