c++lower_bound

时间: 2023-10-15 15:30:08 浏览: 97

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

c lower_bound是一个函数，用于在有序序列中查找第一个大于或等于给定值的元素，并返回该元素的迭代器。它的底层实现是通过二分查找算法来实现的。具体的实现可以参考引用和引用[2]中的代码。在引用的代码示例中，可以看到lower_bound函数的使用方式。它接受一个有序序列的起始和结束迭代器，以及要查找的值作为参数，并返回一个迭代器，指向序列中第一个大于或等于该值的位置。123 #### 引用[.reference_title] - *1* [二分查找及其变种,c++ upper_bound,c++ lower_bound（csdn）————程序.pdf](https://download.csdn.net/download/weixin_44488560/55584670)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"] - *2* *3* [C++ lower_bound() upper_bound() 函数用法详解(深入了解,一文学会)](https://blog.csdn.net/qq_37529913/article/details/125139815)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"] [ .reference_list ]

阅读全文

c++lower_bound

相关推荐

lower-bound函数解释及常用场景.txt

C++ lower-bound()函数.docx

C++ lower_bound

c++ lower_bound

c++lower_bound函数

C++ lower_bound函数

c++ lower_bound高级用法

C++lower_bound函数

c++ lower_bound和upper_bound

c++ lower_bound找不到

C++中lower_bound

c++的lower_bound

c++ set lower_bound

c++中lower_bound

c++中lower_bound用法

c++ map lower_bound

c+++lower_bound

c++ upper_bound 和lower_bound的区别

c++中lower_bound和upper_bound函数用法

最新推荐

tornado-6.4.1-cp38-abi3-musllinux_1_2_i686.whl

Aspose资源包：转PDF无水印学习工具

管理建模和仿真的文件

【R语言高性能计算秘诀】：代码优化，提升分析效率的专家级方法

在构建视频会议系统时，如何通过H.323协议实现音视频流的高效传输，并确保通信的稳定性？

Go语言控制台输入输出操作教程

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

【R语言机器学习新手起步】：caret包带你进入预测建模的世界

在选择PL2303和CP2102/CP2103 USB转串口芯片时，应如何考虑和比较它们的数据格式和波特率支持能力？

红外遥控报警器原理及应用详解下载