二元搜尋 (上) 概念與實作

情境

學姊把 10 雙鞋按尺寸小到大，由左至右收進 10 個盒子。每雙鞋尺寸有可能一樣也有可能不一樣，唯一確定的是越左邊盒子裡的鞋越小，越右邊越大。

1. 一盒一盒打開來看
2. 二元搜尋

兩個方法都可以，但當盒子越多，方法 1 所花的時間會線性成長，而方法 2 是對數成長，所以較為省時。例如，若有 1024 個盒子，方法 1 最多需要開 1024 個盒子，方法 2 只需開 10 個盒子。

年少不知姊姊好

我：「一盒一盒開來看，好慢欸 😧」

學姊：「想學二元搜尋嗎？姊教你 🥰」

概念

在一個排序好的序列中，使用二元搜尋找出自己要的項目，步驟如下：

1. 從中間選一個
2. 根據結果決定往左半或右半找
3. 重複 1 和 2

以開頭的情境為例

• 排序好的 10 個盒子，裡面鞋子的尺寸依序是：
• • 2, 6, 6, 14, 15, 25, 27, 29, 30, 42
• 使用二元搜尋找出 25 號鞋子：
• • 從大約中間的位置開一個盒子
  • • 2, 6, 6, 14, 15, 25, 27, 29, 30, 42
    • 結果是 15 號，小於 25 號
    • 所以 15 號左邊的盒子都不用看了
  • 往 15 號右邊的盒子找
  • 從大約中間的位置開一個盒子
  • • 25, 27, 29, 30, 42
    • 結果是 29 號，大於 25 號
    • 所以 29 號右邊的都不用看了
  • 往 29 號左半邊的盒子找
  • 從大約中間的位置開一個盒子
  • • 25, 27
    • 結果是 25 號，找到了！

實作

使用 python

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # 若沒找到目標，回傳 -1


def print_result(result):
  if result > -1:
    print(f"尺寸 {target} 的鞋子位於第 {result+1} 個鞋櫃")
  else:
    print(f"沒有 {target} 號的鞋子呢")


# 測試
arr = [2, 6, 6, 14, 15, 25, 27, 29, 30, 42]

result = binary_search(arr, 25) # 找 25 號鞋
print_result(result)

result = binary_search(arr, 8) # 找 8 號鞋
print_result(result)

執行結果

$ python binary_search.py
尺寸 25 的鞋子位於第 6 個鞋櫃
沒有 8 號的鞋子呢

「還能繼續嗎？」學姊問。

下一篇：二元搜尋 (下) 技巧與應用