二分的中心思想

二分是一种在单调区间通过取中点层层逼近来寻找极值的算法。二分的中心思想不难，但二分查找时对于边界的处理却是一个永恒的难题，是等于$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<<l或cout<<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;

总结

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