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

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);

Wind_Rises 砂糖老师

2024-08-13 11:37:59

二分系统函数

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的索