C++lower_bound upper_bound二分查找

2026-04-01 15:25:23 231阅读 0评论

C++中的`lower_bound`和`upper_bound`：二分查找的高级应用

在C++中，lower_bound和upper_bound是STL库中非常强大的工具，它们基于二分查找算法，能够高效地在有序容器中查找特定元素的位置。本文将详细介绍这两个函数的用法、原理以及一些实际应用场景。

`lower_bound`的基本概念

lower_bound函数用于找到第一个不小于给定值的元素位置。它的原型如下：

template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

first 和 last 是迭代器范围，表示要搜索的区间。
value 是要查找的值。

如果找到了不小于 value 的元素，lower_bound 返回指向该元素的迭代器；如果没有找到，则返回 last 迭代器。

示例代码

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

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5, 7};
    int target = 4;

    auto it = std::lower_bound(vec.begin(), vec.end(), target);

    if (it != vec.end()) {
        std::cout << "Element found at position: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}

在这个示例中，lower_bound会返回指向第一个等于4的元素的迭代器。

`upper_bound`的基本概念

upper_bound函数用于找到第一个大于给定值的元素位置。它的原型如下：

template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

first 和 last 是迭代器范围，表示要搜索的区间。
value 是要查找的值。

如果找到了大于 value 的元素，upper_bound 返回指向该元素的迭代器；如果没有找到，则返回 last 迭代器。

示例代码

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

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5, 7};
    int target = 4;

    auto it = std::upper_bound(vec.begin(), vec.end(), target);

    if (it != vec.end()) {
        std::cout << "First element greater than " << target << " is at position: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "No elements greater than " << target << std::endl;
    }

    return 0;
}

在这个示例中，upper_bound会返回指向第一个大于4的元素的迭代器。

实际应用场景

1. 查找元素的个数

由于lower_bound和upper_bound可以快速定位元素的边界，因此可以用来计算某个值在有序数组中出现的次数。

int countOccurrences(const std::vector<int>& vec, int target) {
    auto lower = std::lower_bound(vec.begin(), vec.end(), target);
    auto upper = std::upper_bound(vec.begin(), vec.end(), target);

    return std::distance(lower, upper);
}

2. 查找插入位置

lower_bound和upper_bound还可以用来确定新元素应该插入的位置，以保持容器的有序性。

void insertSorted(std::vector<int>& vec, int value) {
    auto it = std::lower_bound(vec.begin(), vec.end(), value);
    vec.insert(it, value);
}

3. 多次查询

对于需要多次查询的场景，预先排序并使用lower_bound和upper_bound可以显著提高效率。

std::vector<int> sortedVec = {1, 2, 4, 4, 5, 7};

for (int i = 0; i <= 7; ++i) {
    auto [lower, upper] = std::make_pair(
        std::lower_bound(sortedVec.begin(), sortedVec.end(), i),
        std::upper_bound(sortedVec.begin(), sortedVec.end(), i)
    );
    std::cout << "Range for " << i << ": [" << std::distance(sortedVec.begin(), lower) << ", " << std::distance(sortedVec.begin(), upper) << ")" << std::endl;
}