🔍 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;
}

        如果你觉得这篇二分笔记对你有帮助，欢迎 👍 收藏，也可以在评论区写下你最常用的模板或踩过的坑，一起进步！