🔍 C++ 二分查找雙模板詳解：左閉右開 vs 左閉右閉（二分筆記）

二分查找（Binary Search）是一類高效的搜索算法，在 O(log n) 的時間復雜度下查找答案，適用于單調性問題。

C++ STL 的 lower_bound / upper_bound 其實也是基于二分的。

今天我們通過兩個常用的 手寫二分模板，來梳理二分查找的思維方法和不同場景的使用技巧。

---

📌 二分查找模板總覽

模板一：找第一個滿足條件的值（左端）

int bsearch_1(int l, int r) {while (l < r) {int mid = l + r >> 1; // 向下取整（mid 偏左）if (check(mid)) r = mid; // 答案在左邊（含 mid）else l = mid + 1;         // 答案在右邊}return l; // or r（此時 l == r）
}

特點：

• 區間：[l, r] 是左閉右閉

• 循環條件：l < r

• 常用于：找最小的滿足條件的值（即最左邊的可行解）

---

模板二：找最后一個滿足條件的值（右端）

int bsearch_2(int l, int r) {while (l < r) {int mid = l + r + 1 >> 1; // 向上取整（mid 偏右）if (check(mid)) l = mid; // 答案在右邊（含 mid）else r = mid - 1;        // 答案在左邊}return l; // or r（此時 l == r）
}

特點：

• 區間：[l, r] 是左閉右閉

• 循環條件：l < r

• 常用于：找最大的滿足條件的值（即最右邊的可行解）

---

🔍 為什么要用兩個模板？

這是很多初學者疑惑的點：為什么還要分兩種模板？能不能一個模板通吃？

答案是：不能，因為不同的問題目標不同。

場景	模板	mid 取法	判斷邏輯
? 最小可行解（左邊界）	模板一	mid = (l + r) / 2	check(mid) 為真則收縮右邊
? 最大可行解（右邊界）	模板二	mid = (l + r + 1)/2	check(mid) 為真則收縮左邊

---

🧪 示例題目：

💡 例題一：給定一個數組，找第一個 ≥ target 的下標

int check(int mid) {return q[mid] >= target;
}
int bsearch_1(int l, int r) { // 找左邊界while (l < r) {int mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}

---

💡 例題二：給定一個數組，找最后一個 ≤ target 的下標

int check(int mid) {return q[mid] <= target;
}
int bsearch_2(int l, int r) { // 找右邊界while (l < r) {int mid = (l + r + 1) >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

---

?? 常見易錯點

錯誤	問題說明
mid = (l + r)/2 直接使用可能溢出	更推薦 mid = l + (r - l)/2 或 l + r >> 1
check(mid) 寫錯邏輯	要明確是“滿足條件”還是“不滿足”
區間定義錯	模板一/二都假設 [l, r] 為閉區間
二分的前提沒保證	只能用于單調性問題，或者題目滿足“有界、有解”

---

? 總結

模板	用于尋找	mid取法	答案縮向
模板一	最小滿足條件的值	mid = (l + r) / 2	r = mid
模板二	最大滿足條件的值	mid = (l + r + 1)/2	l = mid

👉 牢記：左邊界二分向左收縮，右邊界二分向右推進

---

🧩 附：兩者模板的簡寫統一風格

#include<bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int n, m;
int q[N];int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid))r = mid;else l = mid + 1;}return l;
}
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid))l = mid;else r = mid - 1;}return l;
}

????????如果你覺得這篇二分筆記對你有幫助，歡迎 👍 收藏，也可以在評論區寫下你最常用的模板或踩過的坑，一起進步！