分析教材與遞迴教材都把二元搜尋當成 (O(\log n)) 的例子，但沒有處理邊界、lower_bound / upper_bound，也沒有「對答案二分」——後者在課程與實作裡比在陣列裡找一個數更常出現。本篇把迴圈不變量寫死，避免 off-by-one。
相關教材：Chapter2_Algorithm_Analysis_Teaching_Materials.md、Divide_And_Conquer_Teaching_Materials.md、Dynamic_Programming_Teaching_Materials.md（LIS 的 (O(n\log n)) 版本用得到）。
目錄
1. 前提：單調
二元搜尋不是「陣列很長就可以用」。它要求搜尋空間上有一個單調性質：
- 找一個值：陣列已依鍵排序。
- 找一個最小可行答案：
ok(x)一旦為真，所有更大的x也為真（或相反）。
沒有單調性，砍掉一半可能砍掉答案。未排序陣列要先排序，排序的 (O(n\log n)) 通常比直接線性掃描還貴，除非同一陣列要查很多次。
2. 半開區間迴圈
維護半開區間 ([lo, hi))：答案若存在，落在這個範圍的某個索引。
lo = 0, hi = n
while lo < hi:
mid = lo + (hi - lo) / 2 # 不要 (lo+hi)/2，lo 與 hi 很大時會溢位
if a[mid] < target:
lo = mid + 1 # 答案在 mid 的右邊
else:
hi = mid # a[mid] >= target，mid 仍可能是答案
# 結束時 lo == hi，是第一個 >= target 的位置；若 lo == n，表示都小於 target不變量：([0, lo)) 裡的元素都 < target，([hi, n)) 裡的元素都 >= target。mid 的計算用減法，避免 lo+hi 溢位。
這個寫法結束時 lo 就是 lower_bound。若還要確認「真的找到」，再檢查 lo < n && a[lo] == target。
3. lower_bound 與 upper_bound
對已排序陣列：
| 函式 | 回傳的位置 |
|---|---|
lower_bound(target) |
第一個 (\ge target) |
upper_bound(target) |
第一個 (> target) |
upper_bound 只改一個比較方向：if a[mid] <= target: lo = mid+1 else hi = mid。
等於 target 的區間是 [lower_bound, upper_bound)。個數是兩者相減。區間是空的表示不存在。
插入位置也是 lower_bound：插在那裡仍然保持排序。
4. 手算
陣列索引 0..4，值 [1, 3, 3, 5, 8]，找第一個 (\ge 3)。
| 步驟 | lo | hi | mid | a[mid] | 動作 |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 3 | 3 (\ge) 3，hi=2 |
| 2 | 0 | 2 | 1 | 3 | 3 (\ge) 3，hi=1 |
| 3 | 0 | 1 | 0 | 1 | 1 (<) 3，lo=1 |
| 結束 | 1 | 1 | 索引 1 |
第一個 3 在索引 1。upper_bound(3) 會停在索引 3（值 5）。3 出現了 3-1=2 次。
找 4：lower_bound 停在索引 3（值 5），a[3] != 4，所以 4 不存在，但 5 是第一個比 4 大的。
5. 對答案二分
問題不一定長得像「陣列裡有沒有這個數」。只要答案是一個整數、而且可行性單調，就可以二分答案，再用一個線性（或 (n\log n)）的檢查。
問題。 工作時間 [2, 1, 5, 1, 2, 2] 必須依序切成至多 k=3 段連續區間。最小化「最忙那段的總時間」。
單調性：若最大負載 (X) 做得到，更大的 (X) 也做得到。若 (X) 做不到，更小的也做不到。
下界是最長的單一工作 5（一段至少要裝下它）。上界是全部加總 13。
檢查 ok(X)：從左往右掃，目前這段再加下一件會超過 X 就開新段。段數 (\le 3) 則可行。
| X | 切法（一種） | 段數 | 可行？ |
|---|---|---|---|
| 5 | [2,1] [5] [1,2,2] 負載 3,5,5 |
3 | 是 |
| 4 | 5 本身放不進 |
— | 否 |
所以最小可行 (X) 是 5。二分會從 [5, 13] 收到 5。
(k=2) 時 ok(5) 為假，ok(8) 為真：[2,1,5] 與 [1,2,2]。答案是 8。
總時間 (O(n\log S))，(S) 是答案的範圍。檢查若不是線性，把檢查的成本乘上去。
6. 實數二分
答案是實數時沒有「lo==hi」的那一天。改成固定迭代次數（例如 80 次）或 hi-lo 小於公差。
每次仍砍一半。80 次之後區間長度是最初的 (2^{-80})，對多數幾何或工程公差足夠。不要用 while (lo != hi) 比對浮點數。
7. 複雜度
每次丟掉一半，(n) 個元素最多 (\lfloor \log_2 n\rfloor + 1) 次比較。主定理：(T(n)=T(n/2)+\Theta(1)=\Theta(\log n))。
對答案二分是 (O(\log S \cdot C))，(C) 是一次檢查的成本。(S) 若是 (10^{18})，(\log S) 大約 60，通常可以接受；檢查本身是 (O(n^2)) 時，整體可能比另一種演算法差。
8. 常見陷阱
- 閉區間
while (lo <= hi)卻忘記mid+1/mid-1。 會在lo==hi==mid時無限迴圈。半開區間只需要lo < hi，少一個邊界案例。 (lo+hi)/2溢位。lo與hi都超過INT_MAX/2時，和變成負數。用lo + (hi-lo)/2。- 找不到時回傳
lo卻不去看值。lo是插入點，不一定等於 target。 - 對非單調的
ok二分。 例如「段數恰好等於 k」不是單調的，「段數不超過 k」才是。 - 整數答案用實數迴圈。 結束時要決定取
lo還是hi。半開區間的整數版沒有這個歧義。 - 排序是不穩定鍵。 二元搜尋假設比較鍵的順序。用次要鍵排序後，只對主要鍵二分會切到錯誤的一半。
9. C++ 實作
#include <vector>
// 第一個 >= target 的索引；不存在則回傳 n。
int lower_bound_index(const std::vector<int>& a, int target) {
int lo = 0, hi = static_cast<int>(a.size());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
int upper_bound_index(const std::vector<int>& a, int target) {
int lo = 0, hi = static_cast<int>(a.size());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}標準函式庫的 std::lower_bound / std::upper_bound 就是這兩個契約。自己寫之前先確認不變量，不要再發明第三種邊界。
10. 練習題
- 陣列
[2, 4, 4, 4, 7]，lower_bound(4)與upper_bound(4)的索引？4 出現幾次？ lower_bound(1)與lower_bound(8)呢？- 工作
[4, 2, 3, 6]切成至多 2 段，最小的最大負載是多少？ok(8)與ok(9)分別為何？ - 為什麼「找出山峰陣列的頂點」（上升到頂再下降）仍然可以二分，即使它不是全域排序？
- LIS 的 (O(n\log n)) 做法在維護「長度為 k 的最小結尾」。為什麼對這個結尾陣列二分是合法的？
參考答案
- lower 是索引 1，upper 是索引 4，次數
4-1=3。 lower_bound(1)是 0（第一個元素 2 已經 (\ge 1)，但值不是 1）。lower_bound(8)是 5，等於長度，表示全部更小。- 三種切法的最大負載分別是
[4]|[2,3,6]為 11、[4,2]|[3,6]為 9、[4,2,3]|[6]為 9。答案是 9。ok(8)為假：貪婪裝填會得到三段。ok(9)為真：[4,2]與[3,6]。 - 頂點左邊滿足
a[i] < a[i+1]，右邊滿足a[i] > a[i+1]（嚴格山峰）。「中點的右側比較大嗎」是單調的，可以決定往哪一半走。 - 最小結尾陣列本身是遞增的：長度更長的子序列，其最小可能結尾不會比更短的那個更小。遞增才允許二分。
小結
二元搜尋維護一個半開區間，每次用單調性丟掉一半。lower_bound 是第一個大於等於，upper_bound 是第一個大於。對答案二分搜的不是陣列元素，而是「最小的可行參數」，檢查函式必須單調。溢位、無限迴圈、以及在非單調謂詞上二分，是三個固定會出現的 bug。