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

這篇是分享個人在實作 binary search 時，讓它變得更實用的技巧。

直接進入主題。

先看上篇教科書版的 binary_search code，

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. 找不到 target 時是會 return -1，
2. 若 arr 裡有不只一個數字符合 target，會回傳最先找到的 index

我的技巧是在功能的定義做點修正，將改良版 binary_search 規定為：

1. 若找不到 target，return 它該出現的 index
2. 若 arr 裡不只一個數字符合 target，回傳第一個的 index

先舉幾個例子幫助理解，

若 arr = [1, 1, 3, 3, 5, 7, 7]，

• binary_search(arr, 3)
• • returns 2
  • 回傳第一個 3 的 index
• binary_search(arr, 7)
• • returns 5
  • 回傳第一個 7 的 index
• binary_search(arr, 8)
• • returns 7
  • arr 內沒有 8，回傳 8 在 arr 裡該出現的 index
• binary_search(arr, 0)
• • returns 0
  • arr 內沒有 0，回傳 0 在 arr 裡該出現的 index

接續上篇的情境來解釋實用在哪，最後再講實作。

學姊為何要換衣服？為何要綁頭髮？為何呢...

第一種用法，
就是上篇的用法，找出某尺寸的鞋。

arr = [2, 6, 6, 14, 15, 25, 27, 29, 30, 42]
target = 25
index = binary_search(arr, target)

if arr[index] == target:
  print(f"找到啦! {target} 號鞋的 index 是 {index}")
else:
  print(f"沒有 {target} 號鞋..")

執行結果

$ python binary_search.py
找到啦! 25 號鞋的 index 是 5

若把 target 改成 28

$ python binary_search.py
沒有 28 號鞋..

第二種用法，
拿到新一盒鞋子，要放進排好的盒堆中，並保持順序。

arr = [2, 6, 6, 14, 15, 25, 27, 29, 30, 42]
target = 26
index = binary_search(arr, target)
print(f"{target} 號鞋請放在 index = {index} 的位子!")

執行結果

$ python binary_search.py
26 號鞋請放在 index = 6 的位子!

第三種用法，
若乾爹想要買下某尺寸全部的鞋，可以很快地幫他取出來。

arr = [2, 6, 25, 25, 25, 25, 25, 29, 30, 30]
tar = 25

idx1 = binary_search(arr, target)

if arr[idx1] != tar:
  print(f"沒有 {tar} 號鞋  >///<'")
else:
  # 找大一號的鞋子，再把 index 減 1
  idx2 = binary_search(arr, tar + 1) - 1
  print(f"所有 {tar} 號鞋放在 index {idx1} 到 {idx2} 的位子!")

執行結果

$ python binary_search.py
所有 25 號鞋放在 index 2 到 6 的位子!

將 target 改成 31

$ python binary_search.py
沒有 31 號鞋  >///<'

以上簡單分享三種用法，只要將 binary_search 定義清楚，就能這樣應用。

再複習一次改良版 binary_search 定義：

1. 若找不到 target，return 它該出現的 index
2. 若 arr 裡不只一個數字符合 target，回傳第一個的 index

接下來是實作，其實也不難，概念都一樣。

def binary_search(arr, target):
  low, high = 0, len(arr)
  while low < high:
    mid = (low + high) // 2
    if arr[mid] < target:
      low = mid + 1
    elif arr[mid] > target:
      high = mid
    else:
      high = mid
  return low

跟上篇的版本非常類似，留給有興趣的讀者慢慢理解，歡迎留言討論。

偷偷抱怨一下，

code block 真D難用...