二分边界（lower / upper bound）

查找 · 半开区间模板 · 等值区间与计数

重复元素问的不是「在不在」

基础二分返回任意一个命中位置；可数组里有一段 2, 2, 2 时，真正常问的是边界：lower_bound = 第一个 ≥ t 的位置、upper_bound = 第一个 > t 的位置。两界夹出等值区间 [lb, ub)——出现次数 = ub − lb，插入保序的落点也是它。

半开区间：两分支，不特判

模板换成半开区间 [lo, hi)、while (lo < hi)：mid 太小就 lo = mid + 1；否则 hi = mid——注意mid 自己可能就是答案，所以 hi 不减一。没有 found、没有 −1，三分支变两分支，lo 与 hi 相遇点就是答案。下面两阶段找 target = 2：lower_bound 收敛到 1、upper_bound 收敛到 4，最后三个 2 全部点亮。右侧代码随每一步同步高亮。

含重复的有序数组里找 target = 2 的「地盘」。先求 lower_bound：第一个 ≥ 2 的位置。半开区间 [lo, hi) 起手 [0, 10)——hi 是数组外的哨兵位，黄箭头暂不出场

模板的力量

不变量：lo 左边全 < t（或 ≤ t）、hi 起全 ≥ t（或 > t）——收缩永远不丢答案。
不存在：lb == ub，count = 0，无需任何特判；lb 同时是保序插入位。
相遇必答：区间每轮严格缩小，必在答案处相遇——不会死循环。
工程对应：C++ lower_bound / upper_bound / equal_range、Python bisect_left / bisect_right、Java Collections.binarySearch 变体。

「第一个满足条件的位置」这个抽象比「找值」更普适：条件从 ≥ t 换成任何单调谓词（前 false 后 true），模板原封不动——这正是二分答案的入口，也是旋转数组等变形的基石，都在本大类后面几页。