C++上机考试冲刺（四）—排序、查找与二分模板

排序不只是把数据从小到大排列。它经常把一个无序问题转换为能够二分、双指针或分组扫描的问题。查找同样不只是调用 std::find()：数据是否有序、是否需要边界、答案是否具有单调性，会决定应该使用线性查找、标准二分算法还是“对答案二分”。

本篇先整理 C++17 的排序与查找接口，再用一个处理能力规划问题贯穿答案二分的完整过程。

一、排序前先明确目标顺序

1. 基本排序

#include <algorithm>
#include <functional>
#include <vector>

std::sort(values.begin(), values.end());
std::sort(values.begin(), values.end(), std::greater<int>{});

std::sort() 要求随机访问迭代器，因此适用于 std::vector、std::array 和 std::deque，不能直接用于 std::list。对 n 个元素排序通常需要 O(n log n) 次比较。

2. 自定义记录排序

假设记录需要按分数降序、提交时间升序、编号升序排列：

#include <algorithm>
#include <string>
#include <vector>

struct Record {
    int id;
    int score;
    long long submittedAt;
};

std::sort(records.begin(), records.end(),
    [](const Record& left, const Record& right) {
        if (left.score != right.score) {
            return left.score > right.score;
        }
        if (left.submittedAt != right.submittedAt) {
            return left.submittedAt < right.submittedAt;
        }
        return left.id < right.id;
    }
);

比较器回答的是“left 是否应严格排在 right 前面”。相等对象之间必须同时满足 compare(a, b) == false 和 compare(b, a) == false，因此不要使用 <= 或 >=。违反严格弱序要求会导致未定义行为。

3. std::sort() 与 std::stable_sort()

std::sort() 不保证等价元素保持原相对顺序。若数据已经按次要字段排列，只想按主要字段重排并保留原顺序，可以使用 std::stable_sort()；它的稳定性有明确语义，但可能使用更多额外内存。

若所有排序字段都已写进比较器，通常不需要稳定排序。

二、线性查找与二分查找

1. 无序范围：线性扫描

const auto iterator = std::find(values.begin(), values.end(), target);
if (iterator != values.end()) {
    const auto index = std::distance(values.begin(), iterator);
}

单次线性查找是 O(n)。如果只查询一次，先花 O(n log n) 排序未必更快；如果要进行大量查询，排序或建立哈希表才可能值得。

2. 有序范围：三个标准算法

前提是范围已经按同一种顺序排序：

const bool exists = std::binary_search(values.begin(), values.end(), target);

const auto firstNotLess = std::lower_bound(
    values.begin(), values.end(), target
);

const auto firstGreater = std::upper_bound(
    values.begin(), values.end(), target
);

• std::binary_search() 只回答是否存在；
• std::lower_bound() 返回第一个大于等于目标值的位置；
• std::upper_bound() 返回第一个大于目标值的位置；
• 对支持随机访问的有序范围，它们执行 O(log n) 次比较。

3. 统计目标值出现次数

const auto left = std::lower_bound(values.begin(), values.end(), target);
const auto right = std::upper_bound(values.begin(), values.end(), target);
const auto count = std::distance(left, right);

如果数组是 1 2 2 2 5，目标值为 2：

• left 指向第一个 2；
• right 指向 5；
• 半开区间 [left, right) 正好覆盖三个 2。

三、手写边界二分模板

当标准算法不能直接表达判定条件时，可以搜索“第一个满足条件的位置”。对下标区间 [0, n)：

template <typename Predicate>
int firstTrue(int n, Predicate predicate) {
    int left = 0;
    int right = n;

    while (left < right) {
        const int middle = left + (right - left) / 2;
        if (predicate(middle)) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    return left;
}

该模板约定：

• [0, left) 已知不满足；
• [right, n) 已知满足；
• 返回 n 表示没有位置满足条件；
• predicate(index) 必须呈现“先全为假、后全为真”的单调结构。

在考场中，与其背多套 left <= right 的变体，不如先写清区间含义，再保持循环不变量。

四、答案二分的识别方法

有些题目并不是在数组里查找，而是在一个数值范围内寻找最小可行答案。通常具备三个条件：

1. 答案可以落在一个可确定的有序整数区间；
2. 给定候选答案，可以在可接受时间内判断它是否可行；
3. 可行性具有单调性，例如容量越大越容易完成任务。

典型问题包括最小处理能力、最短完成时间、最大允许距离和最小阈值。

五、贯穿场景：最小批处理能力

有 n 个任务，工作量按输入顺序给出。每天必须处理一段连续任务，一个任务不能拆分，要求在 days 天内处理完。求每天至少需要多大的处理能力。

例如工作量为 5 4 3 2 1，要求 3 天完成：

• 能力为 5 时，只能分成 [5] [4] [3,2] [1]，需要 4 天；
• 能力为 6 时，可以分成 [5] [4] [3,2,1]，需要 3 天；
• 因此最小能力为 6。

// verify: cpp17
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

bool canFinish(
    const std::vector<int>& jobs,
    int days,
    long long capacity
) {
    int usedDays = 1;
    long long currentLoad = 0;

    for (int job : jobs) {
        if (job > capacity) {
            return false;
        }

        if (currentLoad + job > capacity) {
            ++usedDays;
            currentLoad = 0;
        }
        currentLoad += job;

        if (usedDays > days) {
            return false;
        }
    }
    return true;
}

long long minimumCapacity(const std::vector<int>& jobs, int days) {
    long long left = *std::max_element(jobs.begin(), jobs.end());
    long long right = std::accumulate(jobs.begin(), jobs.end(), 0LL);

    while (left < right) {
        const long long middle = left + (right - left) / 2;
        if (canFinish(jobs, days, middle)) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    return left;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int days = 0;
    if (!(std::cin >> n >> days) || n <= 0 || days <= 0) {
        std::cout << "INVALID\n";
        return 0;
    }

    std::vector<int> jobs(static_cast<std::size_t>(n));
    for (int& job : jobs) {
        std::cin >> job;
        if (job < 0) {
            std::cout << "INVALID\n";
            return 0;
        }
    }

    std::cout << minimumCapacity(jobs, days) << '\n';
    return 0;
}

输入：

5 3
5 4 3 2 1

输出：

6

边界与复杂度

• 最小可能容量至少是单个任务的最大工作量；
• 最大可能容量是所有工作量之和，此时一天即可完成；
• 容量越大，所需天数不会增加，因此可行性单调；
• canFinish() 是 O(n)；
• 二分次数为 O(log S)，其中 S 是工作量总和；
• 总时间复杂度为 O(n log S)，额外空间为 O(1)，不包含输入数组。

left + (right - left) / 2 避免直接计算 left + right 可能产生的溢出。

六、另外两类代表题

代表题二：区间内元素数量

给定有序数组，统计闭区间 [low, high] 内的元素数量：

#include <algorithm>
#include <vector>

long long countInRange(
    const std::vector<int>& values,
    int low,
    int high
) {
    if (low > high) {
        return 0;
    }

    const auto first = std::lower_bound(values.begin(), values.end(), low);
    const auto afterLast = std::upper_bound(values.begin(), values.end(), high);
    return std::distance(first, afterLast);
}

每次查询需要 O(log n) 次比较。若输入数组无序，应先排序，预处理为 O(n log n)。

代表题三：按绝对值排序

#include <algorithm>
#include <cstdlib>
#include <vector>

void sortByAbsoluteValue(std::vector<long long>& values) {
    std::sort(values.begin(), values.end(),
        [](long long left, long long right) {
            const long long leftAbs = std::llabs(left);
            const long long rightAbs = std::llabs(right);
            if (leftAbs != rightAbs) {
                return leftAbs < rightAbs;
            }
            return left < right;
        }
    );
}

这里增加原值作为次级排序字段，使结果完全确定。若输入可能包含 LLONG_MIN，std::llabs() 无法在 long long 中表示其绝对值，必须改用无符号幅值或根据题目范围另行处理。

七、二分题的调试方法

对小样例手动记录每一轮的 left、middle、right 和判定结果：

left	middle	right	canFinish(middle)	下一步
5	10	15	true	right = 10
5	7	10	true	right = 7
5	6	7	true	right = 6
5	5	6	false	left = 6

循环结束时 left == right == 6。

若程序死循环，优先检查：

• 区间是闭区间还是半开区间；
• middle 在两个元素时是否会一直等于 left；
• 更新边界时是否真正缩小了区间；
• 判定函数是否满足单调性；
• 上界是否保证可行。

八、常见错误

• 在无序数组上直接调用 std::lower_bound()；
• 排序和二分使用了不同的比较规则；
• 比较器使用 <= 或 >=，破坏严格弱序；
• 需要稳定性却使用 std::sort()，或没有必要却依赖稳定排序；
• 把 lower_bound() 当成“必定找到目标值”，没有检查迭代器和元素值；
• 二分区间定义前后不一致；
• 答案二分没有证明判定函数单调；
• 上界并不保证可行；
• 使用 int 保存总和、容量或 left + right。

九、考前速查清单

std::sort(values.begin(), values.end());

const auto left = std::lower_bound(values.begin(), values.end(), target);
const auto right = std::upper_bound(values.begin(), values.end(), target);

while (low < high) {
    const long long middle = low + (high - low) / 2;
    if (feasible(middle)) {
        high = middle;      // 寻找最小可行值
    } else {
        low = middle + 1;
    }
}

• 单次无序查找：先考虑线性扫描；
• 多次精确查询：考虑哈希表；
• 有序边界查询：lower_bound() / upper_bound()；
• 自定义排序：把所有排序字段和方向写清楚；
• 答案二分：先写范围、判定函数和单调性，再写循环；
• 所有总和、容量和中点计算检查整数范围。

十、C++20 可选补充

C++20 的 Ranges 算法支持直接传入范围，例如 std::ranges::sort(values) 和 std::ranges::lower_bound(values, target)。C++17 正文仍使用迭代器对，确保考试环境兼容。

十一、已有专题与延伸练习

• 二分查找：进一步理解边界查找与红蓝染色模型；其中 Ranges 接口属于 C++20，不作为本系列基线。
• 时间复杂度与空间复杂度分析

练习题：

• LeetCode 704：二分查找
• LeetCode 34：在排序数组中查找元素的第一个和最后一个位置
• LeetCode 1011：在 D 天内送达包裹的能力
• LeetCode 875：爱吃香蕉的珂珂

参考资料

• C++17 工作草案 N4659
• Microsoft Learn：<algorithm>
• Microsoft Learn：sort 函数
• Microsoft Learn：lower_bound 函数