lower_bound()和upper_bound()的使用

lower_bound()和upper_bound()的使用

函数 lower_bound()firstlast 中的前闭后开区间进行二分查找,返回不小于 val 的第一个元素位置,如果所有元素都小于 val,则返回 last 位置。

函数原型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class ForwardIterator, class Type>
ForwardIterator lower_bound(
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val
);

template<class ForwardIterator, class Type, class BinaryPredicate>
ForwardIterator lower_bound(
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val,
BinaryPredicate _Comp
);

注意:这里要求查找的区间 / 容器本身是有序的、排好序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
int pos, val;
int nums[8] = { 4, 10, 11, 30, 69, 70, 96, 100 };

pos = lower_bound(nums, nums+8, 3) - nums; // 0
val = *lower_bound(nums, nums+8, 3); // 4
cout << pos << "\t" << val << endl;

pos = lower_bound(nums, nums+8, 9) - nums; // 1
val = *lower_bound(nums, nums+8, 9); // 10
cout << pos << "\t" << val << endl;

pos = lower_bound(nums, nums+8, 30) - nums; // 3
val = *lower_bound(nums, nums+8, 30); / 30
cout << pos << "\t" << val << endl;

pos = lower_bound(nums, nums+8, 111) - nums; // 8
val = *lower_bound(nums, nums+8, 111); // 错误的值,越界
cout << pos << "\t" << val << endl;
return 0;
}

函数 upper_bound()firstlast 中的前闭后开区间进行二分查找,返回大于 val 的第一个元素位置,如果所有元素都小于 val,则返回 last 位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
int pos, val;
int nums[8] = { 4, 10, 11, 30, 69, 70, 96, 100 };

pos = upper_bound(nums, nums+8, 3) - nums; // 0
val = *upper_bound(nums, nums+8, 3); // 4
cout << pos << "\t" << val << endl;

pos = upper_bound(nums, nums+8, 9) - nums; // 1
val = *upper_bound(nums, nums+8, 9); // 10
cout << pos << "\t" << val << endl;

pos = upper_bound(nums, nums+8, 30) - nums; // 4
val = *upper_bound(nums, nums+8, 30); // 69
cout << pos << "\t" << val << endl;

pos = upper_bound(nums, nums+8, 111) - nums; // 8
val = *upper_bound(nums, nums+8, 111); // 错误的值,越界
cout << pos << "\t" << val << endl;
return 0;
}
# C++

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×