跳至内容
Topos Uranos
中文 (中国)

查找与排序

摘要

查找与排序是针对集合的两个基本问题，二者之间存在一种权衡：排序要付出一次代价，却让此后的每一次查找都变得便宜。本课亲手编写线性查找和二分查找，后者在有序数据上每一步都舍弃一半；本课用不变式论证二分查找，证明它会终止，数出它的轮数，并研究毁掉它的三种错误。接着是选择排序和插入排序，以及它们的不变式和比较次数的精确计数；然后用范围库解决同样的问题，并给出决定何时值得先排序再查找的计算。

学习目标

  1. 实现线性查找和二分查找，并用不变式（“如果值存在，它就在 low 和 high 之间”）论证二分查找，同时证明它会终止。
  2. 实现选择排序和插入排序，陈述各自的不变式，并计算它们在最好情况和最坏情况下的比较次数。
  3. 在合适的时候用 std::ranges::sort、std::ranges::contains、std::ranges::find、std::ranges::binary_search 和 std::ranges::lower_bound 代替自己写的版本，并遵守它们的前置条件。
  4. 根据预计的查找次数，判断是否值得先把数据排序再在其中查找，并用比较次数的计数来论证这一判断。

线性查找

查找就是：给定一个集合和一个值，回答这个值是否存在、在哪里。如果对数据的顺序一无所知，就只能逐个查看，别无他法：这就是线性查找。值不存在时，本课程返回 values.size()，即第一个不属于向量的位置：它不是有效的下标，因此不会与某个答案混淆，而且这正是标准库遵循的约定，第五节将会看到这一点。

C++ 程序
#include <cstddef>#include <print>#include <vector>​// 前置条件：无。// 后置条件：返回满足 values[i] == target 的最小下标 i，// 若 target 不存在，则返回 values.size()。std::size_t linearSearch(const std::vector<int>& values, int target){    // 不变式：target 不在 values[0], ..., values[i - 1] 之中。    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}：不存在", target);        } else {            std::println("{}：位置 {}", target, pos);        }    }}
输出
207：位置 3112：位置 1999：不存在

第 10 行的不变式保证了正确性。开始时 i 等于 0，它断言的是关于一个空的部分的事情，因而为真。如果它在一轮开始时成立，且 values[i] 不是要找的值，那么在这一轮结束时，多了一个元素，它仍然成立。不过，循环有两个出口：如果执行了 return i;，那么 values[i] 就是要找的值，并且由不变式可知，它之前的元素都不是，因此 i 是第一次出现的位置（所以出现了两次的 112 报告在位置 1）；如果循环因条件而结束，那么 i 等于 values.size()，不变式说明这个值哪里都没有。循环内的 return 结束了函数，也就随之结束了循环，从而省去了一个标志。

按照算法的代价一课的意义，代价用比较 values[i] == target 来衡量。如果值不存在，恰好要做 nn 次，每个元素一次：这是最坏情况。如果它在位置 pp，要做 p+1p + 1 次。因此，线性查找是 O(n)O(n) 的：数据翻倍，工作量也翻倍。没有额外的信息，就不可能做得更好：一个漏看了某个元素的算法，无法知道那个值是否恰好就在那里。