C++在有序数组中如何查找元素？二分查找与 STL lower_bound/upper_bound 全解

基础概念与目标

有序数组与查找目标

有序数组指的是数组中的元素按照某种全序关系从小到大排列，且该关系对整个序列保持一致。在这样的数据结构中，查找某个元素的目标通常是确定该元素是否存在以及其在数组中的位置。通过对称向中的范围缩小，人们可以快速定位元素是否出现以及所在区间。

查找目标可以是简单地判断存在性，也可以是定位边界（例如最左出现的位置或最右出现的位置）。在有序性保证的前提下，时间复杂度通常可以达到 O(log n)，远优于线性查找。这个性能提升来自于将搜索区间每次折半的策略。

在实际应用中，有序数组不仅限于整型，也可以是字符串、自定义键值对或复合结构，关键在于提供一个稳定的比较准则来维护顺序。理解这一点，对于后续理解二分查找及 STL 的查找工具尤为重要。

二分查找的核心思想

二分查找通过比较中间元素与目标值之间的关系来不断缩小搜索区间。每次比较后，若中间元素小于目标，则目标只能在右半区；反之，则在左半区。这一过程会持续进行，直到找到目标或区间为空为止。

一个关键点是要正确维护区间的边界。常见的实现形式有两种：左闭右闭区间 [low, high] 和 左闭右开区间 [low, high)。两者在边界更新与终止条件上略有差异，但核心原理一致，即通过中点来裁剪搜索区间。

边界处理的正确性直接影响是否能找到第一个匹配项、最后一个匹配项，或是在无解时正确返回特殊值。对于初学者来说，掌握这几种边界情形是实现鲁棒二分查找的基础。

// 简单的二分查找示例：返回目标在有序向量中的下标，未找到返回 -1
template<class T>
int binary_search(const std::vector<T>& a, const T& x) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] < x) {
            l = m + 1;
        } else if (a[m] > x) {
            r = m - 1;
        } else {
            return m;
        }
    }
    return -1;
}

STL 查找工具与原理

std::lower_bound 的含义与用法

std::lower_bound是在有序区间中查找不小于目标值的第一个位置。换句话说，它返回指向区间中第一个使得元素不小于目标值的迭代器。

返回值是一个迭代器，如果目标比区间中的所有元素都大，则返回 end()。这一点对于统计范围、区间计数等操作非常有用。

使用时，要求底层区间具备随机访问迭代器且序列满足严格弱序。通过该工具，可以快速定位目标插入点，从而实现快速查找和区间统计。

#include 
#include 

int main() {
    std::vector<int> v = {1, 2, 2, 3, 5, 7};
    int x = 4;
    auto it = std::lower_bound(v.begin(), v.end(), x);
    // it 指向值 5 的位置，或 end() 如果 x 大于所有元素
    return (it - v.begin());
}

std::upper_bound 的含义与用法

std::upper_bound是在有序区间中查找大于目标值的第一个位置。它返回区间中比目标值大的第一个元素的位置的迭代器。

结合 lower_bound，可以非常方便地得到等于目标值的区间范围。若目标值在区间中出现的次数为 n，则通过 upper_bound 与 lower_bound 的差即可得到该区间的宽度。

该操作与 lower_bound 相辅相成，常用于统计某个值在有序集合中出现的次数、区间定位等场景。

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 2, 3, 3, 3, 4};
    int x = 3;
    auto left = std::lower_bound(v.begin(), v.end(), x);
    auto right = std::upper_bound(v.begin(), v.end(), x);
    // left 指向第一个 3，right 指向第一个大于 3 的位置
    int count = right - left; // 区间内 3 的个数
    return count;
}

std::equal_range 的含义与用法

std::equal_range给出一个区间，包含目标值在有序区间中的所有位置。返回一个二元组（pair），其中第一个迭代器是 lower_bound 的结果，第二个迭代器是 upper_bound 的结果。

通过一对迭代器即可一次性获得目标值的区间范围，以及该区间中的元素数量。这在需要一次性获取区间边界信息时尤为高效。

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

int main() {
    std::vector<int> v = {1, 2, 2, 2, 3, 4};
    int x = 2;
    auto range = std::equal_range(v.begin(), v.end(), x);
    // range.first = lower_bound(v.begin(), v.end(), x)
    // range.second = upper_bound(v.begin(), v.end(), x)
    int count = range.second - range.first;
    return count;
}

实践技巧与示例

查找单个元素的示范代码

在实际代码中，最常见的需求是判断一个值是否在有序数组中存在。如果只需要判断存在性，可以先用 lower_bound 找到插入点，再通过对该位置的前后元素进行等值比较来确定是否存在。

另一种简单直接的做法是结合手写二分查找，返回布尔值或下标。当数组很大时，二分查找的时间复杂度仍然保持为 O(log n)，效率稳定且可预测。

#include <vector>

bool contains(const std::vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] < x) l = m + 1;
        else if (a[m] > x) r = m - 1;
        else return true;
    }
    return false;
}

统计区间内元素个数的实战

当你需要统计某个值在有序数组中出现的次数时，结合 lower_bound 和 upper_bound 最为高效。前者给出左边界，后者给出右边界，两者的差即为计数。

这是很多去重、去重后计数或分组统计中常用的技巧，尤其是在需要对大量数据做范围查询时。

#include <algorithm>
#include <vector>

int count_of(const std::vector<int>& v, int x) {
    auto left = std::lower_bound(v.begin(), v.end(), x);
    auto right = std::upper_bound(v.begin(), v.end(), x);
    return static_cast(right - left);
}

自定义比较与自定义类型的查找

对于自定义类型，你可以提供自定义比较器来保持有序性，并继续使用 lower_bound、upper_bound、equal_range 等 STL 工具。

自定义比较器通常是一个可调用对象，接受两个参数，返回一个布尔值，表示第一参数是否应排在第二参数之前。在使用时将比较器传给相应的 STL 函数即可。

#include 
#include 

struct Item {
    int key;
    std::string name;
};

bool cmp_by_key(const Item& a, const Item& b) {
    return a.key < b.key;
}

int main() {
    std::vector<Item> items = { {1, "A"}, {2, "B"}, {2, "C"} };
    // 根据 key 使用自定义比较器进行查找
    Item target{2, ""};
    auto it = std::lower_bound(items.begin(), items.end(), target, cmp_by_key);
    // 进一步操作：
    return 0;
}

性能与兼容性要点

编译器实现与性能注意点

在多数实现中，std::lower_bound、std::upper_bound 与 std::equal_range 都拥有高效的底层实现，通常会对内存访问模式进行优化，利用缓存局部性提升性能。

注意点包括选择正确的区间边界类型（左闭右闭或左闭右开）、确保输入区间已有序以及对迭代器类型的要求（必须是随机访问迭代器）。如果顺序被破坏，结果将是未定义行为。

在跨平台开发时，尽量使用标准库提供的工具，而不是自己实现同等功能的复杂逻辑，以减少错误并提高可移植性。

处理重复元素的注意点

当数据中存在重复元素时，lower_bound 与 upper_bound 的组合尤其有价值，它们能精确地定位某个键值在有序数组中的全部区间。这在计数、分组、以及后续区间操作中显得尤其重要。

如果你的目标是定位单个匹配项，直接使用二分查找的变体或先调用 lower_bound 再检查等于性的方法都可。对于性能关键的场景，尽量避免额外的比较与拷贝开销。

进阶主题与实操注意

自定义比较下的二分查找策略

在复杂数据结构中，可能需要以多字段排序或自定义排序规则进行查找。此时，std::lower_bound、upper_bound 和 equal_range 与自定义比较器的组合仍然有效。

为避免歧义，确保比较器实现严格弱序，且在两端调用时的行为保持一致。这能确保边界定位不会因为比较逻辑的歧义而产生错误。

// 使用自定义比较器进行查找的示例
#include <algorithm>
#include <vector>

struct Node {
    int a;
    int b;
};

bool comp(const Node& x, const Node& y) {
    // 先按 a 排序，再按 b 排序
    if (x.a != y.a) return x.a < y.a;
    return x.b < y.b;
}

int main() {
    std::vector<Node> v = { {1,2}, {1,3}, {2,1} };
    Node target{1, 2};
    auto it = std::lower_bound(v.begin(), v.end(), target, comp);
    return 0;
}

数据类型与迭代器的选择

若处理的是大型数据集，尽量使用需要的最小数据类型，以减少内存占用和缓存压力。对于容器的选择，std::vector 在大多数二分查找场景中都表现出色，因为它提供了连续的内存布局和良好的局部性。

如果你需要在不可随机访问的序列上进行查找，务必使用合适的适配器或改用其他算法，因为 lower_bound、upper_bound 等需要随机访问迭代器。否则，搜索效率可能显著下降。

实战要点汇总

把握核心时间复杂度与边界行为

核心要点是：在有序数组中查找元素，时间复杂度通常为 O(log n)，通过不断将搜索区间对半分来实现。边界行为决定了你需要的是存在性、位置还是区间范围，选择合适的 STL 工具能让实现变得简洁且正确。

lower_bound、upper_bound、equal_range 三者互补，能够高效完成查找、定位和计数等多种常见任务。学习它们的返回值和语义，对提升代码可读性和性能有直接帮助。

在日常开发中，优先利用标准库提供的实现，必要时再结合自定义比较器来处理复杂类型，以确保代码的稳定性和可维护性。

快速代码片段回顾

下面的代码片段回顾了关键用法，方便在实际项目中快速应用。

// 1) 使用 lower_bound 查找不小于目标的插入点
std::vector<int> data = {1, 2, 2, 3, 5};
auto it = std::lower_bound(data.begin(), data.end(), 3);

// 2) 使用 upper_bound 查找大于目标的插入点，结合可计数
auto it2 = std::upper_bound(data.begin(), data.end(), 3);
int count_of_3 = it2 - it;

// 3) 使用 equal_range 得到目标值的完整区间
auto range = std::equal_range(data.begin(), data.end(), 2);
int count_of_2 = range.second - range.first;