lower_bound&upper_bound - 二分查找函数

他们是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=2int 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=2int num = v[p]; //num=3

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