python中的二分法查找问题

Question

代码如下, 定义好了 Binary 方法, 为什么执行后没有返回结果:

def Binary(t,a):
    a.sort
    low = 0
    high = len(a) - 1
    mid = (low + high) // 2
    while low < high:
        if t < a[mid]:
            high = mid - 1
        elif t==a[mid]:
            print("t is  the in a")
        else:
            low = high + 1
    return


if __name__ == "__main__":
    t = int(input("请输入一个数"))
    a = list(range(1, 20))
    Binary(t, a)

图片描述

Answer 1

你的代碼問題太多了:

1. a.sort 是函數 sort 對象, 由於你沒有調用所以也不會排序, 應當改為 a.sort() 或 a = sorted(a), 不過在不影響原始資料的前提下, 我們通常選擇後者的作法
2. mid 的更新應該在 while 內, 否則不管 low 或是 high 怎麼變動, 你都是在測試一樣的資料
3. low < high 這個條件應當改為 low <= high 否則有一些 corner case 會有問題
4. 當 t > a[mid] 的時候, low 應該更新為 mid + 1 而非 high + 1
5. 當 t == a[mid] 也就是找到目標的時候, 也應該返回該目標的索引值而非打印結果而已
6. 當搜尋結束, 若未發現目標, 應該回傳一個錯誤值, 像是 -1 或是 None, 但我更傾向自定義一個錯誤並引發之

綜上所述加上其他一些小優化包含變量名稱等, 我有一個修正後的版本給你參考:

class NotFoundError(Exception):
    """Can not found target number within the given numbers"""

def binary(target, numbers):
    numbers = sorted(numbers)
    low, high = 0, len(numbers) - 1
    while low <= high:
        mid = (low + high) // 2
        print(low, high, mid)
        if target < numbers[mid]:
            high = mid - 1
        elif target == numbers[mid]:
            return mid
        else:
            low = mid + 1
    raise NotFoundError

target = int(input("请输入一个数"))
numbers = list(range(1, 21))
try:
    idx = binary(target, numbers)
    print('target {} is in numbers with index {}'.format(target, idx))
except NotFoundError as err:
    # error handling

---

我回答過的問題: Python-QA