Alg1.2. 二元搜尋法

在使用排序法 (例如：選擇排序法) 將資料排序完成之後，利用搜尋法從資料中取得特定資料。最簡易搜尋法為循序捜尋，其搜尋方式為從第一筆資料開始依序搜尋特定資料。但是，在大量資料的情況下，循序搜尋法就會遇到效率上的問題。此時，二元搜尋法就成為解決效率問題的替代方案之一。

在使用二元搜尋法時，資料必須要先排序完成。以一個由小到大完成排序的數值串列為例，二元搜尋的概念是以此串列的最中間的數值為中心點，將此串列分成左右兩邊，當資料小於(或大於)中心點的數值時，則可以排除另外一邊的數值，藉此減少搜尋資料的次數。若中心點的數值正是所要的數值時，則回傳該數值及結束搜尋，否則持續搜尋直到結束。

參考檔案：binary_search.py

# 定義函數
def binary_search(data, item):
    low = 0                              # 取得串列頭尾的索引值
    high = len(data) - 1

    while (low <= high):                 # 當串列頭的索引值小於串列尾的索引值
        mid = round((low + high) / 2)    # 取得串列中心點的索引值
        guess = data[mid]

        if guess == item:                # 如果要搜尋的數值等於串列中心點的數值時
            return mid                   # 回傳該數值的索引值
        else:                            # 否則，捨棄某一邊的數值
            if guess > item:
                high = mid - 1           # 捨棄右半邊及更新high
            else:
                low = mid + 1            # 捨棄左半邊及更新low

    return None                          # 若找不到特定數值時，則回傳None


# 呼叫函數
data = [1, 3, 5, 7, 9]
print(binary_search(data, 3))
print(binary_search(data, -1))


# 執行結果
1
None

躍躍欲試

• 使用上述的二分搜尋法:
  • d732: 二分搜尋法 [參考答案] ★★★, practice

參考資料

• 寫程式前就該懂的演算法, 第一章, Aditya Y.Bhargava著, 張書華譯, 松崗, ♥️