整数二分模板

算法思想整数二分的思想主要是如何压缩区间的问题向左压缩或向右压缩以及压缩后左右指针取到的位置考研408模板408的二分查找不太考虑重复元素的情况。查找失败时lowhigh1折半插入排序无重复时lowhigh1,将low和之后的元素后移有重复时midx时仍lowmid1向右压缩,保证稳定性最终也是lowhigh1,将low和之后元素后移26.5.15重新整理比赛模板统一只看结果指针的含义找到和没找到//左右找到是最左那个X没找到在x右边第一个intbsearch_1(inta[],intl,intr,intx){intlll,rrr;while(lr){intmidlr1;if(xa[mid])rmid;elselmid1;}if(lrra[l]x)l;//确保边界性质无歧义没找到就是x右边第一个returnl;}//右左找到是最右边那个x失败在x左边第一个intbsearch_2(inta[],intl,intr,intx){intlll,rrr;while(lr){intmidlr11;if(xa[mid])lmid;elsermid-1;}if(llla[l]x)l--;returnl;}//考研408找到立刻返回(适用于无重复的有重复时位置不确定)没找到也只返回-1intbsearch_3(inta[],intl,intr,intx){while(lr){intmidlr1;if(a[mid]x)returnmid;elseif(xa[mid])rmid-1;elselmid1;}return-1;}后面是之前的笔记模板一两种情况第一个适用于升序数组如1 2 3 3 3 5 6 查找第一个3第二个使用与升序数组如1 2 3 3 3 5 6 查找最后一个3//区间分为[l,mid]和[mid1,r],如下xa[mid]的判断条件使得x要么在[l,mid],要么[mid1,r]//最终l会等于rwhile(lr){intmidlr1;if(a[mid]x)rmid;elselmid1;}//区间分为[l,mid-1]和[mid,r],如下xa[mid]的判断条件使得x要么在[l,mid-1],要么[mid,r]while(lr){intmidlr11;if(a[mid]x)lmid;//不加1死循环条件elsermid-1;}//当一个单调区间中有连续多个x时候第一个模板会取到最左边那个x下标因为xa[mid]时候是边界向左压缩。同理第二个取到最右边的x下标//第二个模板算mid要1因为区间长度为2时mid算出来等于l,而第二个模板存在死循环条件mid给l赋值。2022.3.6//第一个会取到最左边那个符合check条件的下标//第二个会取到最右边那个符合check条件的下标模板二三种情况适用于无重复的有序数组如果存在必定能找到如果不存在l(也等于r1)会等于插入x使得数组仍然有序的位置即最后一定有a [ r ] x a [ l ] a[r]xa[l]a[r]xa[l]就是说x会在r , l r,lr,l之间即时x xx超过了上下界l , r l,rl,r其中一个也会相应地越界比如x m a x xmaxxmax时会有r n − 1 , l n ( 设初始时 l 0 , r n − 1 ) rn-1,ln(设初始时l0,rn-1)rn−1,ln(设初始时l0,rn−1);跳出循环后lr1;这种模板的特点是r可能取到-1l可能取到n 并且由于lmid1,rmid-1所以不存在死循环的情况midlr1计科由于l,r可能存在越界的情况因此最后判断是否找的的时候需要判断是否下标越界一、无重复数字的情况1.这种对x特判找到直接跳出循环 2.如果不存在则r l之间会r l 会分别位于x的两侧while(lr){intmidlr1;if(a[mid]x)returnmid;if(a[mid]x)rmid-1;elselmid1;}二、存在重复数字的情况这种适用于存在重复数字的情况用于找最左边的x或者最右边的x 思想大于等于都向左压缩并且rmid-1,这个-1会使得最后r在小于x的位置1使得l在第一个x的位置一、取最左最终l会等于最左边x的位置不存在则r,l分别在x的两侧while(lr){midlr1;if(a[mid]x)rmid-1;elselmid1;}最终l , r l,rl,r指针会指向什么位置呢从区间压缩的角度看 x xx时r会向左边压缩所以最终r指向 x xx的元素而else即 x xx时l会向右边压缩最终l会指向x的位置,又由lr1,所以l指向最左边的x快速判断方法if else 反着看比如这个模板if(a[mid]x)rmid-1那么最终就是a [ l ] x , a [ r ] x a[l]x,a[r]xa[l]x,a[r]x二、取最右思想小于等于都向右压缩最终r会等于最右边x的位置不存在则r,l分别在x的两侧while(lr){midlr1;if(a[mid]x)lmid1;elsermid-1;}最终l , r l,rl,r指针会指向什么位置呢从区间压缩的角度看 x xx时r会向左边压缩所以最终r指向 x xx的元素而else即 x xx时l会向右边压缩最终l会指向x的位置又由lr1,所以r指向最右边的x这个模板的测试代码#includebits/stdc.husingnamespacestd;inta[10];intmain(){intl0,r10-1,mid;for(inti0;i10;i)printf(%3d,i);coutendl;for(inti0;i10;i){a[i]i*2;printf(%3d,a[i]);}cout\n;intx;cinx;while(lr){midlr1;if(a[mid]x){coutx;break;}elseif(a[mid]x){lmid1;}elseif(a[mid]x){rmid-1;}}coutllendlrrendlmidmid;}测试题 Acwing数的范围第二类模板代码#includebits/stdc.husingnamespacestd;constintN1000005;inta[N];intn,m,x,l,r,mid;intmain(){cinnm;for(inti0;in;i)cina[i];while(m--){cinx;l0;rn-1;while(lr){midlr1;if(a[mid]x)rmid-1;elselmid1;}if(ln||a[l]!x){cout-1 -1endl;}else{inttl;l0;rn-1;while(lr){midlr1;if(a[mid]x)lmid1;elsermid-1;}coutt rendl;}}return0;}例题链接http://noi.openjudge.cn/ch0111/01/01:查找最接近的元素总时间限制: 1000ms 内存限制: 65536kB描述在一个非降序列中查找与给定值最接近的元素。输入第一行包含一个整数n为非降序列长度。1 n 100000。第二行包含n个整数为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。第三行包含一个整数m为要询问的给定值个数。1 m 10000。接下来m行每行一个整数为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。输出m行每行一个整数为最接近相应给定值的元素值保持输入顺序。若有多个值满足条件输出最小的一个。样例输入32 5 82105样例输出85第一类模板代码#includeiostreamusingnamespacestd;constintN1e55;intn,a[N],m,x,l,r,i;boolcheck(intu){//下面两种判断条件都可以//if(a[u]x||a[u]x (x-a[u])(a[u1]-x))return true;//return false;if(a[u]x(x-a[u])(a[u1]-x))returnfalse;returntrue;}intmain(){cinn;for(i0;in;i)cina[i];cinm;while(m--){cinx;l0,rn-1;//二分就是考虑什么时候向左压缩什么时候向右压缩while(lr){在这里插入代码片intmidlr1;//因为mid是下取整所以mid 永远不会取到初始的右边界//同理第二个模板永远不会取到初始的左边界if(check(mid))rmid;//满足条件就向左边压缩elselmid1;//向右边压缩}couta[l]endl;}return0;}第二类模板代码#includebits/stdc.husingnamespacestd;constintN1000005;inta[N];intn,m,x,l,r,mid;intmain(){cinn;for(inti0;in;i){cina[i];}cinm;while(m--){cinx;l0,rn-1;while(lr){midlr1;if(a[mid]x)break;if(a[mid]x)lmid1;elsermid-1;}if(lr)coutxendl;else{if(rn-1)couta[n-1]endl;elseif(l0)couta[0]endl;elseif(abs(a[r]-x)abs(a[l]-x)){couta[r]endl;//注意这里r才是前面的元素}else{couta[l]endl;}}}return0;}还有一种二分的方式例题:leetcode 33. 搜索旋转排序数组 中等 二分classSolution{publicintsearch(int[]nums,inttarget){intnnums.length;intl0,rn-1;while(lr){intmidlr1;if(nums[mid]target)returnmid;if(nums[l]nums[mid]){if(targetnums[l]targetnums[mid])rmid-1;elselmid1;}else{if(targetnums[mid]targetnums[r])lmid1;elsermid-1;}}return-1;}}