binary_search()、lower_bound()和upper_bound()函数在头文件<algorithm>中

1
std::binary_search(begin, end, value);
  • binary_search()函数用于查找指定的元素，找到返回true，否则返回false。

lower_bound()

1
std::lower_bound(begin, end, value);
  • lower_bound()函数返回数组中大于等于value的第一个元素的地址，若数组中的元素均小于value则返回尾后地址。
int a[] lower_bound(a, a + n, 3) - a
[1,2,3,3,3,4] 2
[1,2,2,4] 3
[4,5,6,7,8] 0
[1,1,2,2,2] 5

upper_bound()

1
std::upper_bound(begin, end, value);
  • upper_bound()函数返回数组中大于value的第一个元素的地址，若数组中的元素均小于等于value则返回尾后地址。
vector<int> v lower_bound(v.begin(), v.end(), 3) - v.begin()
[1,2,3,3,3,4] 5
[1,2,2,4] 3
[4,5,6,7,8] 0
[1,1,2,2,2] 5

使用 greater<type>() 重载

1
std::upper_bound(begin, end, value, greater<int>())
  • 在单调不递增的数组中，在数组的 [begin, end) 区间中二分查找小于value的第一个元素的地址，若数组中的元素均大于等于value则返回尾后地址。
1
std::lower_bound(begin, end, value, greater<int>())
  • 在单调不递增的数组中，在数组的 [begin, end) 区间中二分查找小于等于value的第一个元素的地址，若数组中的元素均大于value则返回尾后地址。