Binary Search二分搜尋
lower bound / upper bound 的邊界寫法。
用在：git bisect、字典查詢、版本相容性測試
01為什麼需要它
上週還好好的，今天壞了，中間有一千個 commit。一個一個 checkout 再跑測試，一千次。
為什麼用它commit 是有順序的，而且「好 → 壞」只會翻轉一次：某個 commit 之前全好、之後全壞。測中間那個，好就往後找、壞就往前找，每次砍掉一半，十次就找到。git bisect 做的就是這件事。
套件有 200 個歷史版本，客戶問「最低要哪一版才有這個 API」。
為什麼用它「有沒有這個 API」對版本號是單調的：從某一版開始有，之後都有。要找的是「第一個有的版本」，這正是 lower_bound 回答的問題，八次測試就能定位。
一份依時間排序的 log 有一億筆，要找「10:30 之後的第一筆」；或依字母排序的字典裡找一個字。
為什麼用它資料已經排好，每比一次就能扔掉一半。一億筆只要 27 次比較。「第一筆 ≥ 某時間」就是 lower_bound，這也是資料庫索引查範圍的基本動作。
看到這些關鍵字就想到它：已排序、單調、第一個滿足條件的位置、最後一個不滿足的位置、log n、砍一半、bisect。
02核心概念
二分搜尋只需要一個前提：資料對於你要問的問題是單調的。有序陣列是最常見的形式，但本質是「某個條件在前半全部不成立、後半全部成立」。看中間那個元素，就知道答案在左半還是右半，扔掉另一半。每次砍一半，n 個元素 ⌈log₂(n+1)⌉ 次就到底，這是 O(log n) 的來源。不過要真的做到 O(log n)，還得能直接跳到中間那格：陣列可以，鏈結串列光是走到中間就要 O(n)。
最常見的錯不是想法錯，是邊界寫錯：hi 該是 n 還是 n-1、迴圈是 < 還是 <=、更新是 mid 還是 mid+1，三者必須配套。記住兩套寫法就夠。閉區間 [lo, hi]：hi = n-1，while lo <= hi，兩邊都用 mid ± 1 排除，找到就回傳，適合「找任一個等於 target 的」。半開區間 [lo, hi)：hi = n，while lo < hi，條件成立時 hi = mid（mid 可能是答案，留著），不成立時 lo = mid + 1（mid 確定不是），迴圈結束時 lo == hi 就是答案，適合「找第一個滿足條件的位置」。
lower_bound 是「第一個 ≥ target 的位置」，upper_bound 是「第一個 > target 的位置」，程式碼只差一個等號。它們回傳的是 0..n 之間的插入位置，target 不存在時不會回傳 −1，而是「如果要插入應該放哪」，所以 hi 必須能等於 n。有了這兩個，很多問題直接組合：target 存在嗎，看 lower < n and a[lower] == target；出現幾次，upper − lower；最後一次出現的位置（先確認存在），upper − 1；「最後一個 ≤ target」，upper − 1；「最後一個 < target」，lower − 1。
半開區間為什麼不會無限迴圈：mid = (lo + hi) // 2 向下取整，所以 mid < hi，hi = mid 一定縮小；lo = mid + 1 一定變大。若你寫成「lo = mid」這種不排除 mid 的更新，lo 和 hi 相鄰時 mid 會等於 lo，就卡死了。這時要改成向上取整 mid = (lo + hi + 1) // 2，另一邊配 hi = mid - 1。C++ 裡 lo + hi 可能溢位，寫 lo + (hi - lo) / 2。
03演算法步驟
- 1確認資料對你的條件是單調的：前半全「否」、後半全「是」。把問題改寫成「找第一個『是』的位置」。
- 2選半開區間：
lo = 0，hi = n。答案範圍是0..n，n代表「全部都是否」。 - 3
while lo < hi：mid = (lo + hi) // 2。 - 4條件成立（
a[mid] ≥ target）：hi = mid，mid 留在區間裡。不成立：lo = mid + 1，mid 排除。 - 5迴圈結束時
lo == hi，就是答案。要 upper_bound 把≥改成>；要判斷存在，檢查lo < n and a[lo] == target。
04互動示範
陣列裡 8 出現三次。三個模式對同一份資料、同一個目標：「找任一個」用閉區間，找到就停，回傳的是哪一個 8 沒有保證；lower_bound 和 upper_bound 用半開區間，最後 lo 和 hi 會合的位置就是答案。注意 hi 在半開區間裡是「不含」的，所以可以指到陣列外的 n。
灰色格子已經被排除。lo 和 hi 指向的格子都還在區間裡（閉區間）。
05程式碼
三個函式：經典閉區間版、lower_bound、upper_bound，以及用它們組出「第一次與最後一次出現」。Python 內建 bisect_left / bisect_right、C++ 的 std::lower_bound / std::upper_bound 就是這兩個邊界，會自己寫才知道它們回傳什麼。
# 經典版：閉區間 [lo, hi]，找到任一個 target 就回傳索引，沒有回傳 -1
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi: # 閉區間：lo == hi 時還有一個元素要看
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # mid 已經看過，排除
else:
hi = mid - 1
return -1
# lower_bound：第一個 nums[i] >= target 的 i（不存在就回傳 n）
# 半開區間 [lo, hi)，答案範圍是 0..n，所以 hi 從 n 開始
def lower_bound(nums, target):
lo, hi = 0, len(nums)
while lo < hi: # 半開區間：lo == hi 表示區間空了
mid = (lo + hi) // 2
if nums[mid] >= target:
hi = mid # mid 可能是答案，留在區間裡
else:
lo = mid + 1 # mid 一定不是答案
return lo # 此時 lo == hi
# upper_bound：第一個 nums[i] > target 的 i。只差一個等號
def upper_bound(nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > target:
hi = mid
else:
lo = mid + 1
return lo
# 用兩個邊界回答常見問題
def first_and_last(nums, target): # LeetCode 34
lo = lower_bound(nums, target)
if lo == len(nums) or nums[lo] != target:
return [-1, -1]
return [lo, upper_bound(nums, target) - 1]
if __name__ == "__main__":
a = [2, 5, 8, 8, 8, 13, 21, 34, 55, 89]
print(binary_search(a, 8)) # 4（任一個）
print(lower_bound(a, 8)) # 2
print(upper_bound(a, 8)) # 5
print(first_and_last(a, 8)) # [2, 4]
print(lower_bound(a, 9)) # 5（不存在：插入位置）
# Python 內建：bisect.bisect_left 就是 lower_bound，bisect_right 就是 upper_bound06練習題
- LeetCode 704Binary SearchEasy
- LeetCode 35Search Insert Position（就是 lower_bound）Easy
- LeetCode 278First Bad Version（git bisect 的題目版）Easy
- LeetCode 34Find First and Last Position of Element in Sorted ArrayMedium
- LeetCode 33Search in Rotated Sorted Array（判斷哪半邊有序）Medium
- LeetCode 162Find Peak Element（對「上坡／下坡」二分）Medium