Appearance
二分查找
二分不只是在有序数组中查找某个值，本质是在具有单调性的搜索空间上定位边界。开始前要明确四件事：搜索空间、check(x) 的单调方向、循环不变量，以及退出时答案代表什么。
找第一个满足条件的位置
下面使用闭区间候选值，并让 [left, right] 始终包含可能答案：
cpp
while (left < right) {
const int mid = left + (right - left) / 2;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
// left == right；它是候选答案，必要时仍要确认 check(left)使用 left + (right - left) / 2 可避免 left + right 溢出。不同模板可以使用闭区间或前闭后开区间，但边界初始化、更新规则和退出含义必须成套，不能混用。
有序范围的标准库 API
对于已经按同一比较规则排序的区间 [first, last)，优先使用 <algorithm>：
cpp
auto lower = std::lower_bound(nums.begin(), nums.end(), target); // 首个 >= target
auto upper = std::upper_bound(nums.begin(), nums.end(), target); // 首个 > target
bool found = std::binary_search(nums.begin(), nums.end(), target);这些函数返回迭代器而不是下标。找不到满足条件的元素时，lower_bound / upper_bound 可以返回 end()，解引用前必须检查：
cpp
if (lower != nums.end() && *lower == target) {
std::size_t index = static_cast<std::size_t>(lower - nums.begin());
}带比较器时，排序和二分必须使用等价的比较规则，否则“区间已排序”的前提不成立。
常见变形
- 旋转有序数组：每轮至少有一半有序，据此判断 target 是否位于有序半区；有重复值时可能无法判断方向，收缩边界后最坏退化为 O(n)；
- 答案二分：不是在数组中查值，而是在答案范围上查找首个可行值，例如最小运载能力、最小最大距离；关键是构造单调
check； - 有序矩阵第 K 小：二分答案
x，利用行列单调性在 O(m+n) 内统计<= x的元素数量； - 数值域二分：例如不修改数组寻找重复数，可在值域
[1,n]二分，并用抽屉原理判断方向； - 浮点二分：不能依赖
left == right，应使用固定迭代次数或误差阈值，且明确答案精度。
复杂度与易错点
搜索空间大小为 M 时，二分迭代次数是 O(log M)；总复杂度通常为 O(check 的成本 × log M)，不能只回答 O(log n)。
- 先证明
check单调，再写模板； - 明确找的是第一个
>= target、最后一个<= target，还是任意命中位置； lower_bound返回end()是正常结果，不可直接解引用；- 在答案域二分中，数组长度和搜索范围
M可能不是同一个量； - 更新边界时必须保证区间严格缩小，避免死循环。