C++ 自带的一个函数： upper_bound()

时间: 2023-05-23 12:06:04 浏览: 104

二分查找及其变种,c++ upper_bound,c++ lower_bound（csdn）————程序.pdf

5星 · 资源好评率100%

二分查找是一种高效的查找算法，尤其适用于有序数组。在计算机科学中，它广泛应用于各种数据结构和算法的设计中。本文将深入探讨经典二分查找及其两种变体：`upper_bound` 和 `lower_bound`，并提供C++实现，以及与C++标准库中的对应函数进行对比。 ### 经典二分查找经典二分查找的目标是在一个已排序的数组（或向量）中找到给定值`val`的精确位置。这个位置是`val`在数组内的下标。以下是一个简单的C++实现： ```cpp int* binary_search(int* begin, int* end, int val) { int n = end - begin; int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (*(begin + mid) == val) { return begin + mid; } else if (*(begin + mid) < val) { l = mid + 1; } else { r = mid - 1; } } return end; } ``` 此函数首先计算数组长度`n`，然后使用两个指针`l`和`r`表示搜索范围的左右边界。每次迭代都将中间元素与目标值比较，并根据比较结果更新搜索范围，直到找到目标值或搜索范围为空。 ### 二分变种：`upper_bound` `upper_bound`函数的目的是找到数组中第一个大于给定值`val`的元素的下标。如果不存在这样的元素，它将返回数组末尾的下一个位置。C++实现如下： ```cpp int* binary_search2(int* begin, int* end, int val) { int n = end - begin; int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (*(begin + mid) <= val) { l = mid + 1; } else { r = mid - 1; } } return begin + l; } ``` 这个版本的二分查找在中间元素小于等于`val`时，将左边界移到`mid + 1`，这样可以确保在搜索结束时，`l`指向的位置是大于`val`的第一个元素。 ### 二分变种：`lower_bound` `lower_bound`函数则是寻找数组中第一个大于等于`val`的元素的下标。如果所有元素都小于`val`，它同样会返回数组末尾的下一个位置。C++实现如下： ```cpp int* binary_search3(int* begin, int* end, int val) { int n = end - begin; int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (*(begin + mid) < val) { l = mid + 1; } else { r = mid - 1; } } return begin + l; } ``` 这个版本与`upper_bound`的区别在于，当中间元素小于`val`时，将左边界移到`mid + 1`，使得最终返回的`l`指向的是大于等于`val`的第一个元素。 ### C++标准库中的`upper_bound`和`lower_bound` C++标准库提供了`std::upper_bound`和`std::lower_bound`函数，它们分别实现了上述两种二分查找变体。这两个函数接受一个范围（如数组或向量的迭代器）和一个值作为参数，返回相应位置的迭代器。例如： ```cpp #include <algorithm> int main() { int n3[7] = {1, 2, 3, 3, 4, 5, 6}; int p = 4; auto it = std::lower_bound(n3, n3 + 7, p); // it 现在指向第一个大于等于 p 的元素，即 n3[3] } ``` 对比自定义实现与标准库函数，虽然逻辑相同，但标准库版本通常更高效，因为它们可能利用了编译器优化和内部实现的细节。总结，二分查找及其变体如`upper_bound`和`lower_bound`是解决特定查找问题的强大工具，它们在处理有序数据时具有很好的时间复杂度。通过理解和掌握这些方法，开发者能够编写出更加高效且优雅的代码。同时，了解并使用C++标准库提供的相关函数，可以提高代码的可读性和可维护性。

可以简单地描述一下它的作用吗？ A：可以的。C++ 自带的 upper_bound() 函数用于查找有序数组中第一个大于（或等于）给定值的元素的位置，返回该位置对应的迭代器。该函数在二分查找的基础上实现，时间复杂度为 O(log n)。

阅读全文

C++ 自带的一个函数： upper_bound()

相关推荐

C++ 函数

C++ Queue（带上限的）

C++关联容器操作详解：lower_bound, upper_bound与multimap/multiset的应用

C++ algorithm::lower_bound函数

C++ algorithm::lower_bound函数cmp教程’

C++ STL深入解析：lower_bound函数的运用与实战

c++中lower_bound和upper_bound函数用法

std::binary_search/std::lower_bound

lower_bound函数和upper_bound

STL lower_bound 函数与 upper_bound 函数,

C++中lower_bound和upper_bound的用法

c++ lower_bound和upper_bound

c++ upper_bound 和lower_bound的区别

C++ upper_bound()函数

介绍一下c++中的lower_bound与upper_bound方法

c++ upper_bound

如何实现lower_bound和upper_bound函数？

upper_bound函数

lower_bound/upper_bound使用样例c++，简单版

最新推荐

alexnet模型-通过CNN卷积神经网络的动漫角色识别-不含数据集图片-含逐行注释和说明文档.zip

探索数据转换实验平台在设备装置中的应用

管理建模和仿真的文件

ggflags包的国际化问题：多语言标签处理与显示的权威指南

如何使用MATLAB实现电力系统潮流计算中的节点导纳矩阵构建和阻抗矩阵转换，并解释这两种矩阵在潮流计算中的作用和差异？

使用git-log-to-tikz.py将Git日志转换为TIKZ图形

"互动学习：行动中的多样性与论文攻读经历"

ggflags包的定制化主题与调色板：个性化数据可视化打造秘籍

如何使用Matlab进行风电场风速模拟，并结合Weibull分布和智能优化算法预测风速？

小栗子源码2.9.3版本发布