文章配套练习和题解在【C++题解】排序和二分

我们来详细讲解一下 C++ 标准库中非常重要的 sort 函数以及几个二分查找相关的函数（lower_bound, upper_bound, binary_search, equal_range）。这些函数都位于 <algorithm> 头文件中。

---

std::sort：通用排序函数

std::sort 是一个功能强大且高效的排序函数。它通常采用一种混合排序算法（如内省排序，Introsort），在不同情况下切换使用快速排序、堆排序和插入排序，以保证平均和最坏情况下的时间复杂度都为 O(NlogN)。

1. 基本用法 (默认升序)

最简单的 sort 用法是传入一对指向序列头和尾的迭代器。它会默认按照 < 运算符进行升序排序。

原型：

template<class RandomIt>
void sort(RandomIt first, RandomIt last);

• first: 指向要排序的序列的起始位置的迭代器。

• last: 指向要排序的序列的末尾元素的下一个位置的迭代器（即左闭右开区间 [first, last)）。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

int main() {
    // 对 std::vector 排序
    std::vector<int> v = {5, 2, 8, 1, 9, 4};
    std::sort(v.begin(), v.end()); // 排序整个 vector

    std::cout << "Sorted vector: ";
    for (int i : v) {
        std::cout << i << " ";
    }
    std::cout << std::endl; // 输出: 1 2 4 5 8 9

    // 对 C 风格数组排序
    int arr[] = {7, 3, 0, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::sort(arr, arr + n);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl; // 输出: 0 2 3 6 7

    return 0;
}

2. 自定义排序规则

很多时候，我们需要根据自己的逻辑进行排序，比如降序、按结构体的某个成员排序等。这时可以使用 sort 的重载版本，它额外接收一个比较函数（或函数对象、Lambda表达式）。

原型：

template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

• comp: 一个二元谓词（返回值为 bool 的函数或可调用对象）。 comp(a, b) 如果返回 true，则 a 会被排在 b的前面。

a) 使用普通函数进行降序排序

#include <iostream>
#include <vector>
#include <algorithm>

bool compareDescending(int a, int b) {
    return a > b; // a > b 时，a 排在前面，实现降序
}

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 4};
    std::sort(v.begin(), v.end(), compareDescending);

    for (int i : v) {
        std::cout << i << " ";
    }
    std::cout << std::endl; // 输出: 9 8 5 4 2 1
}

b) 使用 Lambda 表达式 (C++11 及以后推荐)

Lambda 表达式更简洁，可以直接在调用处定义比较逻辑。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 4};
    // 使用 lambda 实现降序排序
    std::sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;
    });

    for (int i : v) {
        std::cout << i << " ";
    }
    std::cout << std::endl; // 输出: 9 8 5 4 2 1
}

c) 对自定义结构体排序

这是一个非常常见的场景。

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

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 95},
        {"Bob", 88},
        {"Charlie", 95},
        {"David", 76}
    };

    // 规则：分数高的在前；分数相同，按名字典序
    std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) {
            return a.score > b.score; // 分数不同，按分数降序
        }
        return a.name < b.name; // 分数相同，按名字升序
    });

    std::cout << "Sorted students:\n";
    for (const auto& s : students) {
        std::cout << "Name: " << s.name << ", Score: " << s.score << std::endl;
    }
}

输出：

Sorted students:
Name: Alice, Score: 95
Name: Charlie, Score: 95
Name: Bob, Score: 88
Name: David, Score: 76

---

二分查找系列函数

核心前提： 使用二分查找系列函数，必须保证操作的区间 已经有序。否则，结果是未定义的。这些函数的时间复杂度都是 O(logN)。

1. std::lower_bound

lower_bound 用于查找第一个不小于（即大于或等于）给定值的元素。

原型：

template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& val);

• 返回值： 返回一个指向第一个不小于 val 的元素的迭代器。如果所有元素都小于 val，则返回 last。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {10, 20, 30, 30, 30, 40, 50};
    //                        0   1   2   3   4   5   6

    // 查找第一个不小于 30 的元素
    auto it1 = std::lower_bound(v.begin(), v.end(), 30);
    // it1 指向索引为 2 的元素 (第一个 30)
    if (it1 != v.end()) {
        std::cout << "First element not less than 30 is: " << *it1 << std::endl;
        std::cout << "Index is: " << std::distance(v.begin(), it1) << std::endl;
    }

    // 查找第一个不小于 35 的元素
    auto it2 = std::lower_bound(v.begin(), v.end(), 35);
    // it2 指向索引为 5 的元素 (40)
    if (it2 != v.end()) {
        std::cout << "First element not less than 35 is: " << *it2 << std::endl;
        std::cout << "Index is: " << std::distance(v.begin(), it2) << std::endl;
    }

    // 查找第一个不小于 60 的元素
    auto it3 = std::lower_bound(v.begin(), v.end(), 60);
    // 找不到，it3 等于 v.end()
    if (it3 == v.end()) {
        std::cout << "No element is not less than 60." << std::endl;
    }
}

2. std::upper_bound

upper_bound 用于查找第一个大于给定值的元素。

原型：

template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& val);

• 返回值： 返回一个指向第一个大于 val 的元素的迭代器。如果所有元素都小于等于 val，则返回 last。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {10, 20, 30, 30, 30, 40, 50};
    //                        0   1   2   3   4   5   6

    // 查找第一个大于 30 的元素
    auto it1 = std::upper_bound(v.begin(), v.end(), 30);
    // it1 指向索引为 5 的元素 (40)
    if (it1 != v.end()) {
        std::cout << "First element greater than 30 is: " << *it1 << std::endl;
        std::cout << "Index is: " << std::distance(v.begin(), it1) << std::endl;
    }
}

lower_bound 和 upper_bound 的组合应用：统计元素个数

在有序序列中，upper_bound 的结果减去 lower_bound 的结果，就是该元素出现的次数。

auto lower = std::lower_bound(v.begin(), v.end(), 30);
auto upper = std::upper_bound(v.begin(), v.end(), 30);
int count = std::distance(lower, upper); // 或者 upper - lower
std::cout << "The number of 30s is: " << count << std::endl; // 输出 3

3. std::binary_search

binary_search 是最直接的二分查找函数，它只告诉你元素是否存在。

原型：

template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& val);

• 返回值： 如果在 [first, last) 范围内找到 val，返回 true；否则返回 false。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};

    if (std::binary_search(v.begin(), v.end(), 30)) {
        std::cout << "Element 30 found." << std::endl;
    } else {
        std::cout << "Element 30 not found." << std::endl;
    }

    if (std::binary_search(v.begin(), v.end(), 35)) {
        std::cout << "Element 35 found." << std::endl;
    } else {
        std::cout << "Element 35 not found." << std::endl;
    }
}

4. std::equal_range

equal_range 可以看作是 lower_bound 和 upper_bound 的结合体。它返回一个 std::pair，包含了等于给定值的所有元素的范围。

原型：

template<class ForwardIt, class T>
std::pair<ForwardIt, ForwardIt> equal_range(ForwardIt first, ForwardIt last, const T& val);

• 返回值： 返回一个 std::pair，其中 pair.first 等价于 std::lower_bound(first, last, val) 的结果，pair.second 等价于 std::upper_bound(first, last, val) 的结果。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
    std::vector<int> v = {10, 20, 30, 30, 30, 40, 50};

    auto range = std::equal_range(v.begin(), v.end(), 30);

    // 打印所有等于 30 的元素
    std::cout << "Elements equal to 30 are: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 计算等于 30 的元素个数
    long long count = std::distance(range.first, range.second);
    std::cout << "Count of 30 is: " << count << std::endl;
}

总结

函数名	功能	返回值
std::sort	对指定范围内的元素进行排序	void
std::binary_search	检查元素是否存在于有序序列中	bool
std::lower_bound	查找第一个不小于val的元素	迭代器
std::upper_bound	查找第一个大于val的元素	迭代器
std::equal_range	查找所有等于val的元素构成的范围	std::pair<迭代器, 迭代器>

掌握这些函数能极大地提高你处理数据和编写算法的效率和代码质量。记住，二分查找系列函数的高效性依赖于数据必须先被排序。