二分处理的边界问题

二分的中心思想

尊彩 www.bz-blog.com 二分是一种在单调区间通过取中点层层逼近来寻找极值的算法。二分的中心思想不难,但二分查找时对于边界的处理却是一个永恒的难题,是等于$mid$还是$mid+1$、$mid-1$?是$l<r$还是$l+1<r$?本文将对二分查找中边界的处理问题进行细致探究。

(本文的诞生背景较为搞笑hhh,起因是作者在新生赛中一道二分题由于对边界处理不懂而瞎jb乱处理导致14发而不AC,于是痛定思痛对于该内容进行细致地研究,遂作本文)

二分的思想主要分为三种:

1.$l$和$r$代表的值都可行,并用变量ans记录答案

2.$l$和$r$代表的值都可行,答案为$l$或$r$

3.仅$l$代表的值可行,答案为$l$

一、二种写法较为常见和简单,第三种就是尊彩有时见到的l+1<r的情况,这种写法不好写还容易错,所以这里不考虑。以下重点讲解一二种写法

二分的边界处理

记录答案法

模板如下:

123456789101112
while(l<r) { int mid=(l+r)/2; if(p(mid)) { ans=mid; r=mid-1; } else l=mid+1; } cout<<ans;

while终止条件是l==r,当左右边界重合时,二分查找结束。

这里尊彩用ans来记录mid的值,p(mid)是个bool函数,表示mid是否符合条件。

当p(mid)为true时,意味着mid符合条件,尊彩把mid记录下来,并缩小范围将右边界缩至mid-1。

 
12
Q:为什么r=mid-1而不是r=mid? A:因为mid已经被ans记录下来,所以这里尊彩在区间中丢弃mid直接将区间缩至mid-1,类似于你将一个文件备份一遍那将其从文件夹中删除也无大碍.

当p(mid)为false时,意味着mid不符合条件,那么直接将左边界缩至mid+1(这里为什么+1就很好理解了,mid本身都不符合条件当然可以扔掉)。

记录答案法的好处是对于边界处理不用太细致。

不记录法

对于不记录法,不同的问题写法不同,主要区别就在于边界的处理上,下面通过四个问题来具体理解理解边界处理的魅力^_^。

1.在一个单调递增区间中寻找第一个大于key的元素

模板这样写:

1234567
while(l<r) { int mid=(l+r)/2; if(a[mid]>key) r=mid; else l=mid+1; } cout<<l;

首先循环条件是l<r,当l=r时查找结束,这时l和r都代表着答案,所以cout<<lcout<<r都行。

其次尊彩来细品这两行:

12
if(a[mid]>key) r=mid; else l=mid+1;

当mid上的值大于key,说明mid目前是符合条件的,既然mid都大于key了,那mid右边的是不是更加大于key了?所以这时尊彩就可以把右边界缩至mid了。那么问题来了,为什么不缩至mid-1呢?因为尊彩前面说了,mid是符合条件的,也就是说mid目前是可行解,如果缩到mid-1,那么尊彩就永远丢失了mid这种情况,有可能导致出错。

下一行,当条件不满足的时候,因为mid本身不符合条件,那mid后面的就更不符合条件了,那直接将没用的mid和更没用的左区间删掉,左边界缩至mid+1。

总结一下,在不记录法中,mid加不加1或减不减1取决于mid本身是否为可行解,是则保留,不是则扔掉。

有了这些基础,另外三道题就可以迎刃而解了。

2.在一个单调递增区间中寻找第一个大于等于key的元素

模板这样写:

1234567
while(l<r) { int mid=(l+r)/2; if(a[mid]>=key)r=mid; else l=mid+1; } cout<<l;

3.在一个单调递增区间中寻找最后一个小于key的元素

模板这样写:

1234567
while(l<r) { int mid=(l+r+1)/2; if(a[mid]<key) l=mid; else r=mid-1; } cout<<l;

注意,敲重点,有没有发现什么不一样的地方?

1
int mid=(l+r+1)/2;

这里的mid为什么要l+r+1呢?举个例子。

如果$mid=(l+r)/2$,当l=2,r=3,mid=2,如果a[2]<key,那么l=mid=2,l没变,接下来将陷入死循环。对于这类问题,尊彩需要将中点右偏。如果$mid=(l+r+1)/2$,当l=2,r=3,mid=3,如果a[3]<key,l=mid=3答案为3,结束循环;如果a[3]>=key,r=2,答案为2,结束循环。

4.在一个单调递增区间中寻找最后一个小于等于key的元素

模板这样写:

1234567
while(l<r) { int mid=(l+r+1)/2; if(a[mid]<=key)l=mid; else r=mid-1; } cout<<l;

总结

对于四种情况的边界处理问题本文都做了详细解释和给出了模板,当对于这些情况都理解透彻后,你一定会发现二分的边界处理也不过如此。

高精度除法
评论
Ayice
文章6
分类1
标签0