二分二分是一种高效的查找算法。当一个有序题目要求的序列a[n]以a[x]1xn为分界线分成两半a[1]~a[x]和a[x1]~a[n]其中一半满足某要求另一半不满足要求现在要求x或者x1的话就可以用到二分。这么说有点绕用一道模板例题来演示有一个长度为n的从大到小的序列a要求最小的大于q的数。思路如果不用二分可以从头往前遍历a找到第一个大于q的数为止这样在最坏情况下的时间复杂度是O(n)。O(logn)优化因为是有序序列那么前面有一段元素就会小于等于q然后从某个元素开始后面的元素就会大于q现在要求出这个分界线就可以所以可以用二分设置两个端点l1rn。l和r之间是可能为答案的元素定义mid(lr)÷2。判断a[mid]是否满足大于q ①如果a[mid]大于q就说明mid之后的数都大于q但是都大于等于a[mid]我们要求最小的大于 q的数所以mid后面的数都不可能是答案mid可能是答案令rmid。 ②如果a[mid]小于等于q那么q之前的数都小于等于q所以mid和mid之前的的数都不可能是 答案就让lmid1。重复2、3步直到lr此时r就是答案。例子n6一个数列a:122356要求第一个大于3的数。设置l1r6。mid(16)/23(保留整数)。a[3]223不可能是答案所以让l314。mid(46)/25。a[5]553可能是答案所以让r5。mid(45)/23(保留整数)。a[4]333不可能是答案所以让l415。此时发现lr所以a[r]——5就是答案!模板程序#includebits/stdc.h using namespace std; const int N1E610; int a[N]; int main(){ int n,q; cinn; for(int i1;in;i)cina[i]; cinq; int l1,rn; while(lr){//重复执行直到lr int mid(lr)/2;//求出mid if(a[mid]q)rmid; //如果a[mid]大于q就说明mid之后的数都大于q但是都大于等于a[mid] else lmid1; //如果a[mid]小于等于q那么q之前的数都小于等于q } couta[r];//a[r]就是答案 return 0; }样例输入61 2 2 3 5 63样例输出5另一个很重要的模板求第一个小于q的数#includebits/stdc.h using namespace std; const int N1E610; int a[N]; int main(){ int n,q; cinn; for(int i1;in;i)cina[i]; cinq; int l1,rn; while(lr){//重复执行直到lr int mid(lr)/2;//求出mid if(a[mid]q)lmid; //如果a[mid]小于q就说明mid之前的数都小于q但是都大于等于a[mid] else rmid-1; //如果a[mid]大于等于q那么q之后的数都大于等于q } couta[l];//a[l]就是答案 return 0; }二分答案二分答案就是二分查找的复杂版要判断的条件复杂了刚才我们判断的条件都是a[mid]q或者a[mid]q但还是满足一段满足条件、另一段不满足条件这个时候我们一般写一个check(x)函数函数返回0、10表示不满足1表示满足。例求一个数的3次方等于q(保证这个在-100~100之间)精确到小数点后3位。这道题涉及到浮点数二分答案但和刚才同理。#includebits/stdc.h using namespace std; const double eps1E-6;//设置精度 int q; bool check(double x){ if(x*x*xq)return 1; else return 0; } int main(){ cinq; double l-100,r100; while(r-leps){//重复执行直到l与r的差小于精度 double mid(lr)/2;//求出mid if(check(mid))lmid; else rmid; } coutfixedsetprecision(3)r; return 0; }lower_bound和upper_bound:lower_bound和upper_bound是C自带的二分函数很好用对于有序递增数组a[1]~a[n]:lower_bound(a1an1q):用二分查找返回数组a第一个大于等于q的元素的迭代器。upperer_bound(a1an1q):用二分查找返回数组a第一个大于q的元素的迭代器。如果没找到就返回a[n1]的迭代器。想转换成下标-a就行时间复杂度O(logn)。例有一个长度为n的从大到小的序列a要求最小的大于等于和最小大于q的数:#includebits/stdc.h using namespace std; const int N1E610; int a[N]; int main(){ int n,q; cinn; for(int i1;in;i)cina[i]; cinq; int ans1lower_bound(a1,an1,q)-a;//迭代器-a int ans2upper_bound(a1,an1,q)-a;//迭代器-a couta[ans1]endla[ans2]; return 0; }以上是二分和lower_bound和upper_bound的一些基本知识。谢谢观看。