二分：

二分是一种高效的查找算法。当一个有序（题目要求）的序列a[n]，以a[x]（1xn）为分界线分成两半（a[1]~a[x]和a[x+1]~a[n]），其中一半满足某要求另一半不满足要求现在要求x或者x+1的话就可以用到二分。

这么说有点绕，用一道模板例题来演示：有一个长度为n的从大到小的序列a，要求最小的大于q的数。思路：如果不用二分可以从头往前遍历a，找到第一个大于q的数为止，这样在最坏情况下的时间复杂度是O(n)。O(logn)优化：因为是有序序列，那么前面有一段元素就会小于等于q，然后从某个元素开始，后面的元素就会大于q，现在要求出这个分界线就可以，所以可以用二分：

1. 设置两个端点l=1，r=n。l和r之间是可能为答案的元素
2. 定义mid=(l+r)÷2。
3. 判断a[mid]是否满足大于q： ①如果a[mid]大于q就说明mid之后的数都大于q但是都大于等于a[mid]，我们要求最小的大于 q的数所以mid后面的数都不可能是答案mid可能是答案，令r=mid。 ②如果a[mid]小于等于q那么q之前的数都小于等于q，所以mid和mid之前的的数都不可能是 答案，就让l=mid+1。
4. 重复2、3步直到l=r，此时r就是答案。

例子：n=6，一个数列a:1，2，2，3，5，6，要求第一个大于3的数。

1. 设置l=1，r=6。
2. mid=(1+6)/2=3(保留整数)。a[3]=2，2<3不可能是答案，所以让l=3+1=4。
3. mid=(4+6)/2=5。a[5]=5，5>3可能是答案，所以让r=5。
4. mid=(4+5)/2=3(保留整数)。a[4]=3，3=3不可能是答案，所以让l=4+1=5。
5. 此时发现l=r所以a[r]——5就是答案!

模板程序：

#include<bits/stdc++.h> using namespace std; const int N=1E6+10; int a[N]; int main(){ int n,q; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cin>>q; int l=1,r=n; while(l<r){//重复执行直到l=r int mid=(l+r)/2;//求出mid if(a[mid]>q)r=mid; //如果a[mid]大于q就说明mid之后的数都大于q但是都大于等于a[mid] else l=mid+1; //如果a[mid]小于等于q那么q之前的数都小于等于q } cout<<a[r];//a[r]就是答案 return 0; }

样例输入：

6

1 2 2 3 5 6

3

样例输出：

5

另一个很重要的模板：求第一个小于q的数：

#include<bits/stdc++.h> using namespace std; const int N=1E6+10; int a[N]; int main(){ int n,q; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cin>>q; int l=1,r=n; while(l<r){//重复执行直到l=r int mid=(l+r)/2;//求出mid if(a[mid]<q)l=mid; //如果a[mid]小于q就说明mid之前的数都小于q但是都大于等于a[mid] else r=mid-1; //如果a[mid]大于等于q那么q之后的数都大于等于q } cout<<a[l];//a[l]就是答案 return 0; }

二分答案：

二分答案就是二分查找的复杂版，要判断的条件复杂了（刚才我们判断的条件都是a[mid]>q或者a[mid]<q）但还是满足一段满足条件、另一段不满足条件，这个时候我们一般写一个check(x)函数，函数返回0、1，0表示不满足，1表示满足。例：求一个数的3次方等于q(保证这个在-100~100之间)，精确到小数点后3位。这道题涉及到浮点数二分答案，但和刚才同理。

#include<bits/stdc++.h> using namespace std; const double eps=1E-6;//设置精度 int q; bool check(double x){ if(x*x*x<q)return 1; else return 0; } int main(){ cin>>q; double l=-100,r=100; while(r-l>eps){//重复执行直到l与r的差小于精度 double mid=(l+r)/2;//求出mid if(check(mid))l=mid; else r=mid; } cout<<fixed<<setprecision(3)<<r; return 0; }

lower_bound和upper_bound:

lower_bound和upper_bound是C++自带的二分函数，很好用

对于有序递增数组a[1]~a[n]:

lower_bound(a+1，a+n+1，q):用二分查找返回数组a第一个大于等于q的元素的迭代器。

upperer_bound(a+1，a+n+1，q):用二分查找返回数组a第一个大于q的元素的迭代器。

如果没找到就返回a[n+1]的迭代器。

想转换成下标-a就行，时间复杂度O(logn)。例：有一个长度为n的从大到小的序列a，要求最小的大于等于和最小大于q的数:

#include<bits/stdc++.h> using namespace std; const int N=1E6+10; int a[N]; int main(){ int n,q; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cin>>q; int ans1=lower_bound(a+1,a+n+1,q)-a;//迭代器-a int ans2=upper_bound(a+1,a+n+1,q)-a;//迭代器-a cout<<a[ans1]<<endl<<a[ans2]; return 0; }

以上是二分和lower_bound和upper_bound的一些基本知识。

谢谢观看。