搭建网站需要什么,上海城乡建设学校网站,做网页专题 应该关注哪些网站,做视频资源网站何为二分#xff1f;形象的说#xff0c;就是单调函数求零点。
我们先对二分查找简单的分析一下#xff08;主要是模板及易错点#xff09;
1.找x的第一个位置#xff1a; 2.找x的第一个位置#xff1a; …何为二分形象的说就是单调函数求零点。
我们先对二分查找简单的分析一下主要是模板及易错点
1.找x的第一个位置 2.找x的第一个位置
while(lr){ while(lr){
mid(lr)/2; mid(lr)/2;
if(a[mid]x) rmid; if(a[mid]x) lmid;
else lmid1; else rmid-1;}
}
首先对于代码1当mid的值大于等于x时说明mid后面都不是目标值但自己不确定。
而当mid的值小于x时说明mid自己及其前面都不是目标值。
所以l到r的区间即为目标值存在的区间所以只要保证两者稳定的逼近一个点即可。
当区间不断变小时对于代码2因为mid的向左取整而l又直接赋值为mid于是可能会进入死循环。而1的话l再mid基础上加了1保证它至少会走1步避免了死循环。
所以代码2只需mid(lr1)/2即可。或者把循环条件改为lr,lmid1;这样就能保证不会陷入死循环不过这样答案在l-1上。
因此法1可以改成lr,rmid-1;
这样子r及其后面一个都可能为答案而终止时lr1;因此l所在的地方即为答案。
特别的当r不动时l一定与R会相等如果此时r还是不动说明无法找到l也指向右边界1
注意一点细节
有时r可能会超int 我们可以用l(r-l)/2来代替。
C STL的二分查找函数
binary_search:返回bool是否存在
lower_bound:返回第一个符合条件的位置 1 2 3 5 6 7搜4时指向5
upper_bound返回最后一个符合条件的位置 1 2 2 3 3 5插3时指向5
下面来一道水题 我们用前缀和维护并分别用二分即可下面是AC代码
