关于c++:函数-lowerboundupperbound

他们是 C ++ 自带的函数，用于在有序的数列里进行查找。留神，肯定是有序的
他们应用的是二分查找的办法，工夫复杂度为 O(logn)，效率很高
应用它们要加上算法头文件，当然，能够应用万能头文件也能够

#include<algorithm> // 算法头文件 
#include<bits/stdc++.h> // 万能头文件

lower_bound – 数列递增序时查找大于等于查找数的第一个数，递加则查找小于等于查找数的第一个数

upper_bound – 数列递增序时查找严格大于查找数的第一个数，递加则严格小于等于查找数的第一个数

能够看出两者应用格局基本相同

lower_bound(begin, end, num);
upper_bound(begin, end, num);

然而它们的返回值是指针或迭代器，咱们要想获取下标还要再减去首地址，晓得了下标也就能够取得具体指了

举几个例子便于了解

数组内应用：

int a[5] = {1, 2, 3, 4, 5}; 
int p = lower_bound(a, a+5, 3)-a; //p=2
int num = a[p]; //num=3

vector 内应用

vector<int> v;
for(int i=1; i<=5; i++)
    v.push_back(i); 
int p = lower_bound(v.begin(), v.end(), 3)-v.begin(); //p=2
int num = v[p]; //num=3

如有疑难欢送在下方评论区提出

lower_bound&upper_bound – 二分查找函数