Algorithm - Binary Search

Binary Search Note

Binary Search 的本質不是「找值」，而是：找邊界（boundary）

幾乎所有題目都可以轉換成：在一個布林序列中，找到某個邊界

F F F F T T T T
        ↑
   找第一個 True

最重要模板（找第一個滿足條件的位置）

適用於：

• lower_bound
• search insert position
• first true
• 最小可行解問題（answer binary search）

int left = 0, right = n;
while (left < right) {
    int mid = (left + right) >> 1;
    if (condition(mid)) right = mid;
    else left = mid + 1;
}
return left;

特性

• 區間：[left, right)
• while 條件：left < right
• right = mid：保留 mid
• left = mid + 1：丟掉 mid

如何設計 condition

1. lower_bound（第一個 >= target）

condition(mid) = nums[mid] >= target;

2. upper_bound（第一個 > target）

condition(mid) = nums[mid] > target;

3. search insert position

condition(mid) = nums[mid] >= target;

找最後一個滿足條件的位置

適用於：

• last true
• 最大可行解

int left = 0, right = n - 1;
while (left < right) {
    int mid = (left + right + 1) >> 1;
    if (condition(mid)) left = mid;
    else right = mid - 1;
}
return left;

特性

• 區間：[left, right]
• mid = (left + right + 1) >> 1：mid 偏右，避免死循環
• left = mid：保留 mid
• right = mid - 1：丟掉 mid

找某個值是否存在

int left = 0, right = n - 1;
while (left <= right) {
    int mid = (left + right) >> 1;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1;

特性

• 區間：[left, right]
• while 條件：left <= right
• 用於「找值是否存在」

判斷更新方式的核心原則

關鍵問題：**mid 還有沒有可能是答案？**

如果 mid 不可能是答案

left = mid + 1;
// 或
right = mid - 1;

如果 mid 可能是答案

right = mid;
// 或
left = mid;

總而言之

解題時優先做這件事：

Step 1：把問題轉成布林條件

F F F T T T

Step 2：決定要找哪個邊界

• 第一個 True
• 最後一個 True

Step 3：套模板

就套唄 (無情)

常見對應關係

題型	condition	模板
lower_bound	nums[mid] >= target	第一個 True
upper_bound	nums[mid] > target	第一個 True
插入位置	nums[mid] >= target	第一個 True
最小可行解	can(mid)	第一個 True
最大可行解	can(mid)	最後一個 True

建議記憶方式

優先記：

1. 找第一個 True（最重要）
2. 找最後一個 True（進階）

不要只記區間形式，因為很容易混亂。

總結

Binary Search 可以統一成兩大類：

• 找第一個滿足條件的位置
• 找最後一個滿足條件的位置

核心在於：

把問題轉成單調的布林判斷（monotonic condition）

這樣可以避免大多數邊界錯誤。