C++ STL 二叉搜索

需要判断某个值是否出现在有序范围中时，可以使用 std::binary_search。它返回表示成员关系的布尔结果；不会返回匹配项的迭代器，也不会返回匹配值的数量。只要满足排序要求，该函数就适用于 vector、数组或其他具有合适迭代器的范围。

理解 std::binary_search 的使用要求

待搜索范围必须按照搜索所用的比较规则进行分区。通常，这意味着元素按照与默认比较规则相同的顺序升序排列。如果范围没有按这种规则排列，搜索结果就不能可靠地表示成员关系。排序后再更改或部分修改元素，也可能破坏这一前提。

这对迭代器表示半开区间 [first, last)：first 指向要检查的第一个元素，last 指向最后一个元素之后的位置，不包含在范围内。传入 container.begin() 和 container.end() 就会搜索整个容器。空范围是有效的，结果表示未找到；对于单元素范围，如果 first 指向该元素而 last 指向其后的位置，那么该元素就包含在范围内。

如果有元素按照排序规则与目标等价，结果为 true；否则为 false。如果需要元素的位置，可以使用 std::lower_bound 等操作，并检查返回的迭代器不等于 last，且对应值与目标值等价。单靠 std::binary_search 无法确定匹配的是哪个重复元素。

在已排序范围中使用 std::binary_search

使用该函数需包含 <algorithm>；输出需包含 <iostream>；此示例使用 vector，因此还需包含 <vector>。下面的完整程序分别检查一个存在的值和一个不存在的值。程序直接使用布尔结果，因此无需依赖迭代器，就能显示这两种结果。

运行此示例：

本节中的代码以及显示的标签或输出仍为英文。

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

int main() {
    const std::vector<int> values{2, 4, 6, 8, 10};
    const bool has_six = std::binary_search(values.begin(), values.end(), 6);
    const bool has_seven = std::binary_search(values.begin(), values.end(), 7);

    std::cout << std::boolalpha
              << "6 found: " << has_six << '\n'
              << "7 found: " << has_seven << '\n';
}

6 found: true
7 found: false

vector 已经排好序，每次调用都会传入它的完整迭代器范围。你可以更改任一目标值来调整示例，但要确保 vector 仍采用搜索所要求的排序规则。该函数不会替你对范围排序。

使用自定义比较器进行搜索

对于用户定义的类型，可以传入一个比较器来定义范围所采用的排序规则。搜索前也要使用同一个比较器排序。在此示例中，记录按年龄排序；只要有记录的年龄与目标年龄相同，搜索就会认为目标存在。姓名不参与此比较器定义的等价规则。

本节中的代码以及显示的标签或输出仍为英文。

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

struct Person {
    std::string name;
    int age;
};

int main() {
    const auto by_age = [](const Person& left, const Person& right) {
        return left.age < right.age;
    };

    std::vector<Person> people{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    std::sort(people.begin(), people.end(), by_age);

    const Person target{"", 25};
    const bool found = std::binary_search(
        people.begin(), people.end(), target, by_age);
    return found ? 0 : 1;
}

比较器比较的是值，而不是迭代器。它必须定义排列范围所用的排序规则，并且能兼容范围元素与目标值之间的比较。在此例中，即使两条记录的姓名不同，只要年龄相同，它们在这次搜索中就等价。如果应用需要区分这些记录，应将用于区分的字段纳入排序规则，或改用其他查找策略。

避免二分搜索中的常见错误

• **搜索未排序的数据：**先对范围排序。按一个键排序、却用另一种排序规则搜索，不符合搜索要求。
• 把 last 当作元素：last 不包含在范围内。要搜索整个容器，请使用 container.end()；不要解引用它。
• **以为会返回迭代器：**返回类型是布尔值。需要位置时请使用 std::lower_bound，并在解引用结果前检查它。
• **使用不匹配的比较器：**排序和搜索必须遵循一致的排序规则和等价关系。如果比较器将两条记录视为等价，成员关系判断就会遵循这条规则，而不是比较记录中的每个字段。

遵循这些检查，函数的结果才有明确意义。标准库会执行搜索，但无法检测范围是否按另一种顺序准备，也无法判断比较器是否与数据匹配。