经典二分库函数

经典二分库函数知识内容Py的bisect库bisect_leftbisect_rightbisect_C的algorithm库lower_boundupper_boundbinary_searchsort简述二分算法检查搜索示例适用附近bin_search例题废案断更周报许久来个存稿知识内容在顺序表中搜索数字我们可以使用二分法以O ( log ⁡ 2 n ) O(\log_2 n)O(log2​n)的复杂读加快搜索过程这里有许多库函数可以使用。Py的bisect库这里重点介绍bisect_left与bisect_right函数。bisect_leftbisect_left函数共有5个参数形式为bisect_left(a,x,lo,hi,key)意义是利用二分法使用key比较方式在顺序列表a[左端lo:右端hi]中寻找待插入元素x的最左合适插入坐标。其中lo、hi还有key可以不输入默认位0、len(a)。如果无法分辨坐标具体性质那么其中返回的坐标i具有如下事实当ilo时x≤a[i]。当loihi时a[i-1]x≤a[i]。当ihi时a[i-1]x。bisect_rightbisect_right函数同样共有5个参数形式为bisect_right(a,x,lo,hi,key)意义是利用二分法使用key比较方式在顺序列表a[左端lo:右端hi]中寻找待插入元素x的最右合适插入坐标。同样lo、hi还有key可以不输入默认位0、len(a)。如果无法分辨坐标具体性质那么其中返回的坐标i具有如下事实当ilo时xa[i]。当loihi时a[i-1]≤xa[i]。当ihi时a[i-1]≤x。bisect_那么更通俗的解释a[i-1]xa[i]在下标i与i-1∈[lo,hi]情况下成立可能会添加在与之相对方向的上。以下是一段实例代码importbisect a1,9,3,5,-1,5,7,9,9fbisect.bisect_left,bisect.bisect_right b0,1,2,4,5,6,8,9,10print(*a)print(*range(len(a)))forxinb:try:print(x,f[0](a,x,2,3),f[1](a,x),a[f[1](a,x)-1])except:print(x,f[0](a,x),f[1](a,x))C的algorithm库这里重点介绍lower_bound、upper_bound与binary_search函数。lower_boundlower_bound函数共有3个参数形式为lower_bound(a.begin(),a.end(),x)意义是利用二分法搜索返回[a.begin(),a.end())范围内首个大于或等于x的元素位置若不存在返回尾迭代器。为方便起见这里沿用lo与hi简写。很显然x≤a[i]。当ilo时x≤a[i]。当loihi时a[i-1]x≤a[i]。当ihi时a[i-1]x。即相当于bisect_leftupper_boundupper_bound函数依旧共有3个参数形式为upper_bound(a.begin(),a.end(),x)意义是利用二分法搜索返回[a.begin(),a.end())范围内首个大于x的元素位置若不存在返回尾迭代器。为方便起见这里仍沿用lo与hi简写。很显然xa[i]。当ilo时xa[i]。当loihi时a[i-1]≤xa[i]。当ihi时a[i-1]≤x。即相当于bisect_rightbinary_searchbinary_search函数依旧共有3个参数形式为binary_search(a.begin(),a.end(),x)意义是利用二分法搜索返回[a.begin(),a.end())范围内的存在与否并不返回位置只返回布尔类型。这里说明这些函数都是适用于有序表所以通常配合sort函数使用sort简述py的排序函数有两种情况一种是列表的方法.sort一种是处理列表用sorted一个返回空类型None将自身排列一个不改变原排列另生成排序表默认升序排序即reverse参数为False。若需要降序可置True也可先升序再用reverse方法。C的sort函数共有3个参数形式为sort(first,last,cmp)cmp是比较方式默认less除此外还存在两种内置存在自动排序机制的数据类型set与map。stable、partial、nth_element、ised等。C中stdlib.h库其实也有qsort函数原型是void qsort(voidbase,size_t num,size_t width,int(__cdeclcompare)(const void*,const void*))。voidqsort(void*base,size_tnum,size_twidth,int(__cdecl*compare)(constvoid*,constvoid*));#includeiostream#includealgorithmusingnamespacestd;voidout(inta[],intl){for(inti0;il;i)couta[i] ;coutendl;}intmain(){inta[]{1,1,3,5,5,5,7,9,9,10};intb[]{0,1,2,4,5,6,8,9,10};intc[]{0,1,2,3,4,5,6,7,8};intl9,i;out(a,9);out(c,9);for(i0;il;i){coutb[i] lower_bound(a1,al,b[i])-a upper_bound(a1,al,b[i])-a a[upper_bound(a1,al,b[i])-a-1] binary_search(a,al,b[i]) endl;}return0;}二分算法常见二分应用于最小值最大化等场景,还可进阶三分。检查搜索示例仅述搜索部分intbis(intL,intR,bool(*check)(int)){while(LR){//一直二分直到区间[L,R]缩小到LRintmid(LR)/2;//mid是L、R的中间值if(check(mid))Rmid;//答案在左半部分[L,mid]更新为RmidelseLmid1;//答案在右半部分[mid1,R]更新为Lmid 1}returnmid;/*实际使用时会存在差异*/}还有defbis(L,R,check):whileLR:mid(LR)//2;ifcheck(mid):Rmid;else:Lmid1;returnmid#(LR)1,L(R-L)/2适用三种实现适用场合可能出现的问题mid(leftright) /2left≥0right≥0leftright无溢出1leftright可能溢出2负数情况下有向0取整问题L(R-L)/2r-l无溢出若r和l都是大数且一正一负r-l可能溢出(LR)1lr无溢出若r和l都是大数lr可能溢出右中位数,前驱后驱12L(R-L1)/2(leftright1) 1附近第一个大于位置upper_bound第一个大于或等于lower_bound第一个相等lower_bound最后一个相等upper_bound-最后一个小于或等于upper_bound-最后一个小于位置lower_bound-个数upper_bound-lower_boundll,ur,u,≥l,-≤u-,-l-,a[i-1]xa[i],~bin_search类似lower_boundintbin_search(int*a,intn,intx){//a[0]~a[n-1]是单调递增的intleft0,rightn;//注意不是n-1,此时是左闭右开的[0,n)while(leftright){intmidleft(right-left)/2;//mid ( left right) 1;if(a[mid]x)rightmid;/*r-*/elseleftmid1;}//终止于 left rightreturnleft;//特殊情况a[n-1]x时返回n}例题「lanqiaoOJ2145」求阶乘3539」买二赠一22废案7、bisect1bisect_left(a,x,lo,hi,key)利用二分法使用key比较方式在顺序列表a[左端lo:右端hi]中寻找待插入元素x的合适插入坐标若是right返回最右侧换言之一般情况下a[i-1]x≤a[i]right则a[i-1]≤xa[i]特殊情况下即ilo时仅有x≤a[i]ihi时仅有a[i-1]xright则ihi时仅有a[i-1]≤xilo时仅有xa[i]。例题3539买二赠一。————————————————