lower_bound复杂度

lower_bound的时间复杂度是O(logn)，其中n是数组的大小。这是因为lower_bound使用了二分查找算法，在一个排好序的数组中查找给定值。具体来说，它通过比较数组中间元素和目标值的大小来确定目标值可能出现的位置，然后将搜索范围缩小到该位置的左侧或右侧，直到找到目标值为止。由于每次比较都将搜索范围减少一半，所以时间复杂度是O(logn)。因此，lower_bound的时间复杂度是O(logn)。

相关问题

lower_bound时间复杂度

lower_bound的时间复杂度是O(log n)。这是因为lower_bound是使用二分查找的算法实现的，它可以在有序数组中找到第一个大于或等于目标值的元素的位置。在每一次查找中，它将数组的中间元素与目标值进行比较，然后根据比较结果确定下一次查找的范围。通过将查找范围逐渐缩小一半，lower_bound可以在O(log n)的时间复杂度内找到目标值的位置。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [关于set中使用lower_bound 和 upper_bound 的时间复杂度](https://blog.csdn.net/mountain_hua/article/details/115790311)[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^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [C++的STL进一步总结之lower_bound和upper_bound](https://blog.csdn.net/weixin_36416680/article/details/79958167)[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^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]

multiset.lower_bound时间复杂度

multiset自带的lower_bound函数的时间复杂度为O(logn)，其中n为multiset中元素的个数。lower_bound函数返回一个迭代器，指向第一个不小于给定值的元素。如果multiset中不存在不小于给定值的元素，则返回multiset.end()。需要注意的是，lower_bound函数只能用于有序容器，如set和multiset。