二分边界（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 是数组外的哨兵位，黄箭头暂不出场
1function lowerBound(a: number[], t: number): number {
2 let lo = 0, hi = a.length; // 半开区间 [lo, hi)，hi=n 哨兵
3 while (lo < hi) {
4 const mid = (lo + hi) >> 1; // 探针
5 if (a[mid] < t) lo = mid + 1; // 太小：答案在右
6 else hi = mid; // ≥ t：mid 可能就是答案
7 }
8 return lo; // 相遇点 = 第一个 ≥ t
9}
10// upperBound：把 < 换成 <=（等于也右走）→ 第一个 > t
11// 个数 = upperBound − lowerBound
target2
阶段lower_bound
[lo, hi)[0, 10)（hi=n 哨兵）
mid—
1 / 14
模板的力量
不变量：lo 左边全 < t（或 ≤ t）、hi 起全 ≥ t（或 > t）——收缩永远不丢答案。
不存在：lb == ub，count = 0，无需任何特判；lb 同时是保序插入位。
相遇必答：区间每轮严格缩小，必在答案处相遇——不会死循环。
工程对应：C++
不存在：lb == ub，count = 0，无需任何特判；lb 同时是保序插入位。
相遇必答：区间每轮严格缩小，必在答案处相遇——不会死循环。
工程对应：C++
lower_bound / upper_bound / equal_range、Python bisect_left / bisect_right、Java Collections.binarySearch 变体。 「第一个满足条件的位置」这个抽象比「找值」更普适：条件从 ≥ t 换成任何单调谓词（前 false 后 true），模板原封不动——这正是二分答案的入口，也是旋转数组等变形的基石，都在本大类后面几页。