算力手记C++ & COMPUTING SYSTEMS

CHAPTER 20 / 数据结构与算法

二分、排序与堆：保留哪些候选

找第一个不小于目标的位置，为什么比“找相等”更好复用？

阅读与推演约 60 分钟练习时间另计

这一章要弄清楚

  • 用半开区间写正确二分
  • 解释排序和选择的不同需求
  • 用小根堆维护最大的 k 项

先备知识：算法与lambda：表达处理意图 / 测试与调试：独立定位失败 / 数组、哈希与双指针：重复工作从哪里删掉

ISO C++20；macOS 或 Linux；仅标准库；示例是独立教学程序，非学习者验收。

二分依赖的是单调边界

给定升序数组，寻找第一个不小于目标的下标，可以把问题转换为一串判断：前面元素小于目标，后面元素不小于目标，目标是两段之间的边界。即使数组没有等于目标的值，边界仍有意义；如果所有元素都小于目标，答案就是 size。这个定义天然覆盖空数组、重复值和插入位置，比只找“某个相等值”更容易说明合同。

维护半开候选区间 [lo,hi)，初始是零到 size。每轮取中间位置 mid；若中间值小于目标，mid 及之前都不可能是答案，令 lo=mid+1；否则答案可能就是 mid，令 hi=mid。循环结束 lo==hi，这个位置就是边界。不要把闭区间模板里的减一更新随意混进来，否则容易漏掉候选或死循环。

中点和进度都需要证明

使用 lo+(hi-lo)/2 避免直接求 lo+hi 的溢出，但仍依赖 lo≤hi 且差值可表示。每轮必须严格缩短区间：小于分支抛弃 mid，另一分支把 hi 收到 mid；这也是为什么不能在小于分支写 lo=mid。用长度一和长度二的区间手算，最容易发现无法前进的错误。

标准库 lower_bound 表达相同边界能力，其前提是范围相对目标满足分区关系；完全排序是常见充分条件。对随机访问迭代器，比较与移动都有效率；对链表等非随机访问迭代器，比较次数可对数但迭代器推进仍可能线性。复杂度应该说清计算的是什么操作。

不需要全序时，不一定要完整排序

排序把全部元素放入顺序，适合之后反复查找、合并和报告。找最大 k 项则只需要保留一小部分候选。维持容量最多 k 的小根堆：堆顶是当前保留集合里最小的值，新值加入后若超过 k，就丢掉最小值。因为它已经不可能属于已读数据的最大 k 项，排除是安全的。

对流输入，每读一个值做一次对数 k 级调整，整体 O(n log k)，额外空间 O(k)。若 k 接近 n，完整排序可能更简单，且要输出有序结果时还需整理保留项。priority_queue 默认是大根堆，要保留最大的 k 个数，反而需要小根堆方便删除最差候选，这个方向常被写反。

堆只保证局部关系

二叉堆保证父子之间符合优先关系，不保证底层数组整体有序。top 给最高优先级元素，pop 调整结构后给下一个。不要遍历内部表示就声称已得到排序结果。建堆可在线性时间完成，而逐个插入是另一种成本；选择实现时要区分已有整批输入和持续流式输入。

本章先用二分找到重复值的最左位置，再用大小三的小根堆处理 [5,1,9,3,7]，保留 [5,7,9]。练习覆盖空、全小、全大、重复值和 k=0、k>n。每次移动或删除候选，都能解释为什么被删元素不可能影响最终答案，这才是算法可靠性的核心。

观察 · 推演

lower_bound([1,3,3,7],3)

lo0hi4mid/value2 / 301 / 04 · MEMORYlo0hi4mid/value2 / 301 / 04 · MEMORY
初始区间

mid=2，值 3 不小于目标，因此保留左半含 mid。

1 / 4
阅读完整推演文字
  1. 初始区间

    lo：0；hi：4；mid/value：2 / 3

    mid=2，值 3 不小于目标，因此保留左半含 mid。

  2. 区间 [0,2)

    lo：0；hi：2；mid/value：1 / 3

    mid=1，值仍为 3，hi 收为 1。

  3. 区间 [0,1)

    lo：0 → 1；hi：1；mid/value：0 / 1

    mid=0，值 1 小于 3，lo 更新为 1。

  4. 边界相遇

    answer index：1；value：3

    lo=hi=1，第一个不小于 3 的位置是 1。

跟着例子，走完一遍

例题 01C++20 · 本机可运行

第一个不小于目标的位置

升序数组 [1,3,3,7]，找 3；同时检查 8、0 和空输入。

  1. lo=0,hi=4，mid=2，值 3，hi=2。
  2. mid=1，值 3，hi=1。
  3. mid=0，值 1，lo=1；答案 1。
16-a.cpp
下载
#include <iostream>
#include <span>
#include <vector>
std::size_t lower(std::span<const int> values, int target) {
    std::size_t lo = 0, hi = values.size();
    while (lo < hi) {
        const auto mid = lo + (hi - lo) / 2;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
int main() {
    const std::vector<int> values{1, 3, 3, 7};
    if (lower(values, 3) != 1 || lower(values, 8) != 4 || lower(values, 0) != 0 ||
        lower(std::span<const int>{}, 3) != 0) return 1;
    std::cout << "lower=" << lower(values, 3) << " after-end=" << lower(values, 8) << '\n';
}

如何编译和运行下载的 .cpp 文件 →

结果与解释

lower=1 after-end=4

保留 mid 为候选才能找到最左相等项；不存在时返回插入边界。

在本机运行这个例子

下载后，在文件所在目录执行。需要支持 C++20 的编译器；POSIX 示例还需要章节说明中的系统条件。

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 16-a.cpp -o example && ./example

预期标准输出：

lower=1 after-end=4
例题 02C++20 · 本机可运行

小根堆保留最大三项

数据 [5,1,9,3,7]，k=3；最终从小到大输出保留值。

  1. 前三项保留 1、5、9。
  2. 读 3 后丢 1。
  3. 读 7 后丢 3，保留 5、7、9。
16-b.cpp
下载
#include <functional>
#include <iostream>
#include <queue>
#include <span>
#include <vector>
std::vector<int> largest(std::span<const int> input, std::size_t k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    for (const int x : input) {
        heap.push(x);
        if (heap.size() > k) heap.pop();
    }
    std::vector<int> result;
    while (!heap.empty()) { result.push_back(heap.top()); heap.pop(); }
    return result;
}
int main() {
    const std::vector<int> values{5, 1, 9, 3, 7};
    const auto top = largest(values, 3);
    if (top != std::vector<int>{5, 7, 9} || !largest(values, 0).empty() ||
        largest(values, 10).size() != values.size()) return 1;
    for (std::size_t i = 0; i < top.size(); ++i)
        std::cout << (i == 0 ? "" : " ") << top[i];
    std::cout << '\n';
}
结果与解释

5 7 9

小根堆顶是保留集合最差候选；被淘汰值不可能进入当前最大三项。

在本机运行这个例子

下载后，在文件所在目录执行。需要支持 C++20 的编译器；POSIX 示例还需要章节说明中的系统条件。

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 16-b.cpp -o example && ./example

预期标准输出：

5 7 9
常见错误

混用二分边界约定

半开区间却在 hi 分支减一，或 lo=mid 使长度一时不前进。

修正思路：明确 [lo,hi) 不变量；小于时 lo=mid+1，否则 hi=mid，手算长度 0、1、2。

轮到你动手

先写预测或代码，再按需打开提示。完整答案用于对照自己的推理。

练习 1

数组 [2,2,2] 分别找 1、2、3 的 lower_bound。

给我一点提示
  1. 答案可以等于 size。
  2. 重复值要最左位置。
查看答案与推理

分别是 0、0、3。目标 1 插在最前；目标 2 第一项已满足；目标 3 所有项都小于它，因此答案是尾后下标。

练习 2

最大 k 项为什么用小根堆，而最小 k 项要用大根堆？

给我一点提示
  1. 堆顶应该是最容易淘汰的保留项。
  2. 每次超容量就删最差候选。
查看答案与推理

保留最大值时，集合最小值最差，需小根堆快速淘汰；保留最小值时相反。堆顶代表保留边界，不一定代表整道题想要的最大或最小。

把理解说出来

先用中文讲清因果，再用英文回答。问题依据技能主题编写，并非公司内部题库。

解释

二分为什么不一定需要找相等？

参考回答 / English answer

单调谓词的真假边界更一般，lower_bound 即找第一个不小于目标的位置，也支持未命中插入。

Binary search locates a monotone boundary. Lower_bound finds the first value not below the target, even when no equal value exists.
预测

所有值小于 target，lower_bound 返回哪里？

参考回答 / English answer

返回 size/结束迭代器，不能直接解引用。

It returns the past-the-end position. The caller must check that boundary before dereferencing it.
找错

lo=mid 为什么可能死循环？

参考回答 / English answer

当 hi=lo+1，mid=lo，小于分支不改变 lo，区间不缩短。

With a one-element interval, mid equals lo. Assigning lo back to mid makes no progress, so the loop can repeat forever.
复杂度

流式 top-k 的时间和空间是什么？

参考回答 / English answer

小堆容量至多 k，平均每项对数 k 调整，总 O(n log k)、空间 O(k)，k=0 单独理解为常数边界。

A bounded heap uses logarithmic work in k per retained update and O(k) space. For positive k, the total bound is O(n log k), with trivial handling for k zero.
追问

堆底层数组是整体排序的吗？

参考回答 / English answer

不是，只维持父子优先关系；按顺序输出需反复 pop 或额外排序。

A heap only enforces its parent-child ordering invariant. Producing a sorted sequence requires repeated extraction or another sorting step.
设计

lower_bound 在链表上一定整体 O(log n) 吗？

参考回答 / English answer

比较次数对数不等于迭代推进对数；非随机访问迭代器的移动可能线性。

The number of comparisons can be logarithmic while iterator advancement is linear. Random access matters for the full operation cost.

继续查证

公开资料用于查证；本章图解和例题是独立教学内容。CPU 逻辑模型不能证明设备性能。

接着看已有的图解

这些资料按主题补充本章内容。