1

root 站长 2019-07-11 16:41:02 2024-10-19 20:03:55 27

STL 查找

lower_bound 函数

用于在一个升序序列中查找某个元素,并返回第一个不小于该元素的元素的迭代器,如果找不到,则返回指向序列中最后一个元素之后的迭代器。
假设后面的实例均在数组 a 中,包含 n 个元素,查找 x。

int k = lower_bound(a + 1, a + 1 + n, x) - a;

如果没有比这个数字大的就返回 n + 1。

upper_bound 函数

用于在一个升序序列中查找某个元素,并返回第一个大于该元素的元素的迭代器,如果找不到,则返回指向序列中最后一个元素之后的迭代器(减a变成下标)。

int k = upper_bound(a + 1, a + 1 + n, x) - a; 如果没有比这个数字大的就返回 n + 1。

binary_search 函数

用于确定某个元素有没有在一个升序序列中出现过,返回 true 或 false。

int k = binary_bound(a + 1, a + 1 + n, x);

{{ vote && vote.total.up }}

共 11 条回复

Wind_Rises 砂糖老师

二分系统函数

binary_search(a, a+n, v):在数组 a 中查找元素 v 是否存在;若是查到了v返回1,查找不到则返回0。

lower_bound(a, a+n, v):从数组的 begin 位置到 end-1 位置二分查找第一个大于或等于v的数字,找到返回该数字的地址,不存在则返回end;可以通过减去首地址得到索引。

upper_bound(a, a+n, v):从数组的begin位置到end-1位置二分查找第一个大于v的数字,找到返回该数字的地址,不存在则返回end;可以通过减去首地址得到索引。

int n = 14;
int a[14]={1, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 9, 9, 10};           //升序数组
cout << binary_search(a, a + n, 8) << endl;                      //0,没找到  
cout << binary_search(a, a + n, 4) << endl;                      //1,找到了
cout << lower_bound(a, a + n, 4)- a << endl;                     //4,第一个>=4的索引
cout << upper_bound(a, a + n, 4)- a << endl;                     //8,第一个>4的索引
int a[14]={10, 9, 9, 7, 6, 5, 4, 4, 4, 4, 3, 2, 2, 1};           //降序数组
cout << binary_search(a, a + n, 8, greater<int>()) << endl;      //0,没找到
cout << binary_search(a, a + n, 5, greater<int>()) << endl;      //1,找到了  
cout << lower_bound(a, a + n, 4, greater<int>())- a << endl;     //6,第一个<=4的索引
cout << upper_bound(a, a + n, 4, greater<int>())- a << endl;     //10,第一个<4的索 
elk

9(6翻了)

ykj49 Accepted

999 i

chj20120517

栓Q

cjy116

能发代码吗?

ddd

So?

ddd
Xionghaoyu straight a student

然后呢?

Xionghaoyu straight a student

然后呢?

haoyuexiaozi 精神小伙

xuedaole!!!