auto_ai 知识库

Appearance

蓝红划分是二分查找的一种通用模板，通过维护"蓝色区域"和"红色区域"的边界，统一解决"查找第一个满足条件的元素"和"查找最后一个满足条件的元素"等边界问题。核心是定义 isBlue() 函数，将数组分为蓝（满足条件）和红（不满足条件）两部分。

定义与核心原理 ​

传统二分查找容易在边界条件上出错（+1/-1、死循环）。蓝红划分通过统一的模板消除这些问题：

  • 蓝色区域：满足 isBlue() 条件的元素
  • 红色区域：不满足 isBlue() 条件的元素
  • 目标：找到蓝红交界处的指针 l（最后一个蓝色）和 r（第一个红色）

四种常见查询 ​

以数组 [1, 2, 3, 5, 5, 5, 8, 9]，目标值 5 为例：

查询类型isBlue 条件返回结果
第一个 ≥ 5nums[mid] < 5r索引 3（元素 5）
最后一个 < 5nums[mid] &lt; 5l索引 2（元素 3）
第一个 > 5nums[mid] ≤ 5r索引 6（元素 8）
最后一个 ≤ 5nums[mid] ≤ 5l索引 5（元素 5）

操作步骤 ​

标准模板 ​

cpp
int lower_bound(vector<int>& nums, int target) {
    int l = -1, r = nums.size();  // 开区间 (l, r)
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) {  // isBlue 条件
            l = mid;  // 蓝色扩张
        } else {
            r = mid;  // 红色扩张
        }
    }
    return r;  // 第一个不满足 isBlue 的位置
}

关键要点 ​

  1. 初始边界：l = -1, r = n，覆盖整个数组的开区间
  2. 循环条件：l + 1 &lt; r，确保区间内至少有一个元素
  3. 无死循环：mid 始终在 (l, r) 内，每次迭代区间至少缩小 1
  4. 返回值选择：
    • 要"第一个满足 X"→ 用 isBlue = !X，返回 r
    • 要"最后一个满足 X"→ 用 isBlue = X，返回 l

最终状态示意 ​

以数组 [0,1,2,3,4,5,6,7,8]，查找"第一个 ≥ 5"为例（isBlue = &lt; 5）：

索引:  0   1   2   3   4 | 5   6   7   8
值:    0   1   2   3   4 | 5   6   7   8
      └──── 蓝色 ────┘   └─── 红色 ────┘
                    l=4   r=5

循环结束时 l + 1 == r，蓝色区域为 [0, l]，红色区域为 [r, n-1]。返回 r=5 即第一个 ≥ 5 的元素索引。

实践应用 ​

  • 有序数组查找：lower_bound / upper_bound 的标准实现
  • 旋转数组查找最小值：isBlue = nums[mid] > nums[0]
  • 峰值查找：isBlue = nums[mid] &lt; nums[mid+1]
  • 答案二分：在解空间上二分，isBlue = check(mid)

常见误区 ​

  1. 混淆 l 和 r 的含义：l 始终是最后一个蓝色，r 始终是第一个红色，不要混用
  2. isBlue 条件写反：想找"第一个 ≥ target"，isBlue 应该是 &lt; target（蓝色是小于 target 的部分）
  3. 闭区间和开区间混用：蓝红划分是开区间模板，不要写成 l &lt;= r 的闭区间形式

一句话总结 ​

蓝红划分用 isBlue() 把数组切成蓝、红两段，开区间 l = -1, r = n 配 while (l + 1 &lt; r) 保证不死循环；找第一个满足 X 的返回 r，找最后一个满足的返回 l。

相关概念 ​