标准答案
- 使用 [left, right) 区间，初始 right 为数组长度。
- 若 array[mid] >= target，记录可能答案并令 right = mid；否则令 left = mid + 1。
- 返回 left；若 left 等于长度，表示不存在满足条件的位置。时间复杂度 O(log n)。
题目解析
lower_bound 查找的是满足 values[i] >= target 的最小下标，不是任意命中位置。命中后仍要收缩右边界，让左侧可能存在的重复值继续参与搜索。
使用左闭右开区间 [left, right) 时，right 初始化为 length，循环条件是 left < right。循环结束时 left 既可能指向第一个满足条件的位置，也可能等于 length 表示不存在。
重复元素、空数组、目标小于最小值和大于最大值都能由同一套边界处理。每轮区间至少缩短一个位置，时间 O(log n)，额外空间 O(1)。
代码示例
lower_bound 实现：
TypeScript
function lowerBound(values: number[], target: number) {
let left = 0, right = values.length
while (left < right) {
const mid = left + Math.floor((right - left) / 2)
if (values[mid] >= target) right = mid
else left = mid + 1
}
return left
}常见误区
- 误区：命中后立即返回。改正：记录候选并继续向左收缩，直到找到第一个满足条件的位置。
- 误区：混用闭区间和半开区间边界。改正：明确区间定义，左闭右开时 right 应为 length。
- 误区：把返回 length 当成数组元素。改正：length 表示没有满足条件的位置，调用方要单独处理。