st语言 upper_bound
时间: 2024-01-15 12:03:54 浏览: 26
在 C++ 中,`upper_bound` 是一个函数模板,用于在一个已排序的序列中查找第一个大于某特定值的元素的位置,它的定义如下:
```c++
template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);
```
其中,`first` 和 `last` 分别是指向序列起始和结束位置的迭代器,`value` 是要查找的特定值。这个函数返回一个迭代器,它指向序列中第一个大于 `value` 的元素的位置。如果序列中所有元素都小于等于 `value`,则返回 `last`。
需要注意的是,序列必须已经按照某种规则排序,否则结果将是未定义的。`upper_bound` 函数使用的是二分查找算法,因此时间复杂度为 $O(\log n)$。
相关问题
ST语言中upper_bound lower_bound的用法
在 ST 语言中,`upper_bound` 和 `lower_bound` 也用于在一个已排序的序列中查找指定值的位置。它们的使用方法与 C++ 中的函数类似,但有一些细节需要注意。
1. `upper_bound` 函数
`upper_bound` 函数的语法如下:
```
pos:= upper_bound(array, value [, compare])
```
其中,`array` 是要查找的已排序数组,`value` 是要查找的特定值,`compare` 是一个可选参数,用于指定比较函数。返回值 `pos` 是一个整数,它表示第一个大于 `value` 的元素的位置。
需要注意的是,与 C++ 不同,ST 语言中的 `upper_bound` 函数返回的位置是从 0 开始计数的,而不是从 1 开始。此外,如果 `value` 大于等于数组中的所有元素,则返回数组长度。
下面是一个使用 `upper_bound` 函数的例子:
```
array := [1, 2, 2, 3, 4, 5]
pos := upper_bound(array, 2)
// pos 的值为 3,表示第一个大于 2 的元素在数组中的位置为 3
```
2. `lower_bound` 函数
`lower_bound` 函数的语法与 `upper_bound` 函数类似,但它返回的是第一个大于等于 `value` 的元素的位置。即,如果数组中存在元素等于 `value`,则返回第一个等于 `value` 的元素的位置;否则返回第一个大于 `value` 的元素的位置。
```
pos:= lower_bound(array, value [, compare])
```
需要注意的是,ST 语言中的 `lower_bound` 函数也返回从 0 开始计数的位置,而不是从 1 开始。如果 `value` 大于数组中的所有元素,则返回数组长度。
以下是一个使用 `lower_bound` 函数的例子:
```
array := [1, 2, 2, 3, 4, 5]
pos := lower_bound(array, 2)
// pos 的值为 1,表示第一个大于等于 2 的元素在数组中的位置为 1
```
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
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)