upper_bound什么意思

时间: 2023-05-27 21:07:08 浏览: 68

二分查找及其变种,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++标准库提供的相关函数，可以提高代码的可读性和可维护性。

upper_bound 是一个函数，用于在已排序的序列中查找某个值第一次出现的位置，如果不存在，则返回大于该值的第一个位置。通俗点说，就是找到一个位置，使得该位置的值大于等于给定值，但是该位置前面的值都小于给定值。

阅读全文

upper_bound什么意思

相关推荐

Upper confidence bound_python_Confidence_

BFS_Branch_and_Bound

upper_bound 和 lower_bound

ower_bound和upper_bound

lower_bound/upper_bound

lower_bound 和 upper_bound

upper_bound和lower_bound

upper_bound

c++ lower_bound和upper_bound

set中的lower_bound和upper_bound

lower_bound函数和upper_bound

upper_bound和lower_bound不重复吗

def generate_random_number(lower_bound, upper_bound): return random.uniform(lower_bound, upper_bound)

二叉树的lower_bound和upper_bound

upper_bound用法

upper_bound函数

set的upper_bound

如何实现lower_bound和upper_bound函数？

STL lower_bound 函数与 upper_bound 函数,

最新推荐

SSM Java项目：StudentInfo 数据管理与可视化分析

管理建模和仿真的文件

负载均衡技术深入解析：确保高可用性的网络服务策略

怎么解决头文件重复包含

pyedgar：Python库简化EDGAR数据交互与文档下载

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

网络监控工具使用宝典：实时追踪网络状况的专家级技巧

unity 实现子物体不跟随父物体移动和旋转

Node.js环境下wfdb文件解码与实时数据处理

关系数据表示学习