二分查找：思路很简单，细节是魔鬼
二分查找模板：
intsearch(inta[],intn,intv){intleft=0;intright=n-1;//注意:右边界写的是n-1while(left=right){//注意：小于等于=，主要是为了防止漏掉边界值intmid=(right+left)/2;if(a[mid]==v)returnmid;elseif(a[mid]v)left=mid+1;//注意：抛弃左边部分elseif(a[mid]v)right=mid-1;//注意：抛弃右边部分}return-1;}
while循环中的不等号是否应该带等号？
①：while（left=right）终止条件left==right+1,区间形式[3,2]，跳出时搜索完毕，正常跳出
②：while（leftright）终止条件left==right,区间形式[2,2]，跳出时区间内还有值，非正常跳出，忽略了边界值。
mid是否应该加一？
①：缩小查找范围
二分查找：查找等于v的值
#includeiostreamusingnamespacestd;ints(inta[],intn,intv){intleft=0,right=n-1;while(left=right){intmid=(left+right)1;if(a[mid]v){left=mid+1;}elseif(a[mid]v){right=mid-1;}else{returnmid;}}}intmain(){inta[8]={1,2,3,4,5,6,7,8};couts(a,8,6)endl;return0;}
寻找左侧边界模板：
intsearch(inta[],intn,intv){intleft=0;intright=n;//注意:右边界写的是nwhile(leftright){//注意：这里是intmid=(right+left)/2;if(a[mid]==v)right=mid;//不确定是不是第一个所以保留elseif(a[mid]v)left=mid+1;elseif(a[mid]v)right=mid;//大于目标值，可以直接作为边界}returnleft;}
图解：
返回了下标1：第一个大于等于目标值的下标为1，也可以说小于目标值2的的元素有1个
二分查找：查找第一个大于等于v
#includeiostreamusingnamespacestd;ints(inta[],intn,intv){intleft=0,right=n;while(leftright){intmid=(left+right)1;//求第一个大于等于目标数值的情况if(a[mid]v){left=mid+1;//mid向左全部舍弃(包含mid)}else{//a[mid]=vright=mid;//mid向右全部舍弃(不包含mid)}//if(a[mid]=v){//也是求第一个大于等于的值//right=mid;//}else{//left=mid+1;//}}returnleft;}intmain(){inta[8]={1,2,3,4,5,6,7,8};couts(a,8,6)endl;return0;}
寻找右侧边界模板：
intsearch(inta[],intn,intv){intleft=0;intright=n;//注意:右边界写的是nwhile(leftright){//注意：这里是intmid=(right+left)/2;if(a[mid]==v)left=mid+1;//等于小于都不是大于所以向右推进elseif(a[mid]v)left=mid+1;elseif(a[mid]v)right=mid;//大于目标值，可以直接作为边界}returnleft;}
图解：
返回了下标3：也就是说第一个大于目标2的下标为3
二分查找：第一个大于v
#includeiostreamusingnamespacestd;ints(inta[],intn,intv){intleft=0,right=n;while(leftright){intmid=(left+right)1;//求第一个大于目标数值的情况if(a[mid]value){//也是求第一个大于的值right=mid;}else{left=mid+1;}//if(a[mid]=v){//也是求第一个大于的值//left=mid+1;//}else{//right=mid;//}}returnleft;}intmain(){inta[8]={1,2,3,4,5,6,8,8};couts(a,8,6)endl;return0;}
二分答案：在一个区间内二分地枚举答案，每找到一个答案，则判定其是否满足题目条件。如果满足，则去寻找更好的解；如果不满足，则去尝试更劣一些的解，看其是否满足。
P：（二分答案）
程序代码：
#includeiostream#defineLLlonglongusingnamespacestd;constintN=1e5+10;constintM=1e8;inta[N];intmain(){intn,k;cinnk;longlongcount=0;//支持19位for(inti=0;in;i++){cina;count+=a;}if(countk){cout0endl;return0;}intleft=0,right=M;while(leftright){intmid=(left+right)/2+1;//除法是向下取整的//intmid=(left+1+right)/2也可以这样写count=0;for(inti=0;in;i++){count+=a/mid;}if(countk){right=mid-1;//选取的中间值偏大，向左移动，mid右边得都大}else{left=mid;//如果大于等于，舍去mid左边的，继续选取最优值}}coutleftendl;return0;}一只小跃跃