鍍金池/ 問答/Python  數(shù)據(jù)庫/ python中的二分法查找問題

python中的二分法查找問題

代碼如下, 定義好了 Binary 方法, 為什么執(zhí)行后沒有返回結(jié)果:

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("請(qǐng)輸入一個(gè)數(shù)"))
    a = list(range(1, 20))
    Binary(t, a)

圖片描述

回答
編輯回答
寫榮

你的代碼問題太多了:

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

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

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("請(qǐng)輸入一個(gè)數(shù)"))
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

2018年3月29日 14:33