二分查找——红蓝染色法

二分查找的核心不是"猜中目标"，而是将数组染成红蓝两色，答案就是红蓝交界处。

基本问题

查找有序数组中第一个 >= target 的位置。若全部 < target，返回数组长度。

算法核心——染色逻辑

设定红蓝两种颜色：

颜色	含义	区间
红色（false）	`< target`	`[0, L-1]`
蓝色（true）	`>= target`	`[R+1, n-1]`

循环不变量：每次迭代后，[0, L-1] 一定为红色，[R+1, n-1] 一定为蓝色。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
初始状态
[ ?, ?, ?, ?, ?, ?, ?, ? ]
  L=0                   R=7

循环进行中
[ R, R, R, ?, ?, B, B, B ]
     L-1  L     R  R+1

循环结束（L > R）
[ R, R, R, R, B, B, B, B ]
          R  L
          ↑  ↑
        红蓝交界处：L（或 R+1）就是答案

关键规则：

M 染色为红色时：L = M + 1（排除 [0, M]）
M 染色为蓝色时：R = M - 1（排除 [M, n-1]）

L = M + 1 而非 L = M——当区间只剩一个元素时，L = M 会进入死循环。

Go 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func lowerBound(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1  // 染红：排除 [0, mid]
        } else {
            right = mid - 1 // 染蓝：排除 [mid, n-1]
        }
    }
    return left // 或 right+1
}

变体

变体	染色条件	返回值
第一个 `>= target`	`< target` 染红	`left`
第一个 `> target`	`<= target` 染红	`left`
最后一个 `< target`	`< target` 染红	`right`
最后一个 `<= target`	`<= target` 染红	`right`

用"染什么色"统一理解四种变体，不再背 left/right/mid±1。

循环不变量是二分查找的证明

循环不变量在循环的每一轮前后都成立：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
循环开始前：
  [0, -1] 为空 → 满足"全红"
  [n, n-1] 为空 → 满足"全蓝"
  ✓ 不变量成立

每次迭代：
  M 染红 → 保持 [0, L-1] 全红
  M 染蓝 → 保持 [R+1, n-1] 全蓝
  ✓ 不变量保持

循环结束（L > R）：
  [0, L-1] 全红 且 [R+1, n-1] 全蓝
  L = R+1 → 红蓝恰好相邻
  ✓ L 即为第一个蓝色元素的位置

循环不变量成立 + 区间每次严格缩小 → 算法收敛到正确答案。不需要特殊处理边界——循环不变量保证了边界正确性。

目录

算法 — 速查手册

二分查找——红蓝染色法

基本问题

算法核心——染色逻辑

Go 实现

变体

循环不变量是二分查找的证明