upper_bound什么意思
时间: 2023-05-27 10:07:08 浏览: 38
upper_bound 是一个函数,用于在已排序的序列中查找某个值第一次出现的位置,如果不存在,则返回大于该值的第一个位置。通俗点说,就是找到一个位置,使得该位置的值大于等于给定值,但是该位置前面的值都小于给定值。
相关问题
upper_bound 和 lower_bound
upper_bound和lower_bound是C++标准库中的两个函数,用于在有序的容器(例如数组或vector)中查找指定的元素。
upper_bound函数返回的是容器中第一个大于指定元素的位置,而lower_bound函数返回的是容器中第一个大于等于指定元素的位置。
这两个函数接收三个迭代器参数,分别是容器的起始位置、结束位置和要查找的元素。它们都使用了二分查找算法来实现,因此在有序容器中的查找速度非常快。
下面是它们的用法示例:
int arr[] = {1, 2, 2, 3, 4, 4, 5};
vector<int> vec(arr, arr + 7);
sort(vec.begin(), vec.end());
auto it1 = upper_bound(vec.begin(), vec.end(), 3); // 返回指向元素4的迭代器
auto it2 = lower_bound(vec.begin(), vec.end(), 4); // 返回指向元素4的迭代器
cout << "upper_bound: " << *it1 << endl;
cout << "lower_bound: " << *it2 << endl;
输出结果为:
upper_bound: 4
lower_bound: 4
ower_bound和upper_bound
lower_bound和upper_bound函数是用于在一个有序数组中进行查找的函数。lower_bound函数返回大于等于给定值的第一个元素的位置,而upper_bound函数返回大于给定值的第一个元素的位置。这两个函数都利用了二分查找的方法,在有序数组中进行查找,时间复杂度为O(log n)。需要注意的是,使用这两个函数的前提是数组必须是有序的。在数组中使用lower_bound和upper_bound函数时,可以通过减去数组的起始位置来得到相对位置。在STL中,也提供了lower_bound和upper_bound函数,使用时需要包含相应的头文件。<span class="em">1</span><span class="em">2</span><span class="em">3</span><span class="em">4</span>