《算法圖解》第一章學習心得

二分法學習要點：僅當清單是有序的時候， 二分查找才管用。 如按英文字母表排序的電話簿。時間複雜度為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