二分查找的边界写法：下界、上界与答案二分

大多数 off-by-one 来自：区间开闭不一致、中点更新方向与不变量冲突。下面用半开或闭区间中选一种，全程坚持。

下界（第一个 ≥ target）

func lowerBound(a []int, target int) int {
    lo, hi := 0, len(a) // [lo, hi)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if a[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

上界（第一个 > target）

把判断改成 a[mid] <= target 时 lo = mid + 1，其余相同。上界减下界即等于 target 的个数。

答案二分

当解空间单调（「最小的可行 x」），对答案本身二分，用 check(mid) 收缩区间。注意 check 的单调性证明，否则会静默错解。

习惯 dual

• 中点用 lo + (hi-lo)/2，避免溢出（在大整数语言里仍是好习惯）。
• 先写不变量注释，再写循环。
• 空数组、单元素、全小于 / 全大于 target 必须过单测。

小结

二分是纪律题。模板可以背，但只有不变量清晰时，改题才不慌。