二分的模板

二分查找元素要求数组的有序性,或者拥有类似与有序的性质。

本题要找到不小于该元素的最小位置和不大于该元素的最大位置, 两个界限,所以写两个二分

查找不小于 x 的第一个位置, 代码如下:

int l = 0, r = n - 1;

while(l < r)
{
    int mid = l + r >> 1;
    if(a[mid] < x) l = mid + 1;
    else r = mid;
}

 查找第二个位置:

int l = 0, r = n - 1;
while(l < r)
{
    int mid = l + r + 1 >> 1;
    if(a[mid] <= x) l = mid;   边界划分为 l = mid 时, mid要加 1
    else r = mid - 1;
}

完整代码:

#include <iostream>
using namespace std;
const int maxn = 100005;
int n, q, x, a[maxn];
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
    while (q--) {
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] < x)  l = mid + 1;
            else    r = mid;
        }
        if (a[l] != x) {
            printf("-1 -1\n");
            continue;
        }
        int l1 = l, r1 = n;
        while (l1 + 1 < r1) {
            int mid = l1 + r1 >> 1;
            if (a[mid] <= x)  l1 = mid;
            else    r1 = mid;
        }
        printf("%d %d\n", l, l1);
    }
    return 0;
}

如果想深入思考 

当a[mid]小于x时,令l = mid + 1,mid及其左边的位置被排除了,可能出现解的位置是mid + 1及其后面的位置;当a[mid] >= x时,说明mid及其左边可能含有值为x的元素;当查找结束时,l与r相遇,l所在元素若是x则一定是x出现最小位置,因为l左边的元素必然都小于x。查找不大于x的最后一个位置,便不容易了:

int l1 = l, r1 = n;
while (l1 + 1 < r1) {
    int mid = l1 + r1 >> 1;
    if (a[mid] <= x)  l1 = mid;
    else    r1 = mid;
}
要查找不大于x的最后一个位置,当a[mid] <= x时,待查找元素只可能在mid及其后面,所以l = mid;当a[mid] > x时,待查找元素只会在mid左边,令r = mid。
为什么不令r = mid - 1呢?因为如果按照上一个二分的写法,循环判断条件还是l < r,当只有两个元素比如2 2时,l指向第一个元素,r指向第二个元素,mid指向第一个元素,a[mid] <= x,l = mid还是指向第一个元素,指针不移动了,陷入死循环了,此刻l + 1 == r,未能退出循环。
那么直接把循环判断条件改成l + 1 < r呢?此时一旦只有两个元素,l和r差1,循环便不再执行,查找错误。
所以这里出现了二分的典型错误,l == r作为循环终止条件,会出现死循环,l + 1 == r作为循环终止条件,会出现查找错误。
问题如何解决,一种方法就是将查找的区间设置为左闭右开,比如待查找元素在[0,n - 1]范围内,可以写成[0,n),令r = n,这时候只有两个元素时,r是取最右边元素的后一个位置的,l和r相差2,还会执行循环。
现在再来理解上一段的r1 = mid,说明a[mid] > x时,r = mid就表示待查找元素会是在r的左边,因为r是开区间。上面这种写法修改了循环条件使得二分不会死循环,修改了区间的开闭性使得不会查找错误。另一种解决办法就是:

int l = 0, r = n - 1;
while (l < r)
 {
        int mid = l + r + 1 >> 1;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
 }
不修改循环终止条件,想办法解决死循环的问题,首先想下为什么查找不小于x的第一个位置不会死循环?因为这时就算只有两个元素,l + 1 = r,mid = l,a[mid]小于x时l是会+1的,不小于x时r = mid也会缩小区间。
而查找不大于x的最后一个位置之所以会死循环是因为编程语言里面除以2的下取整性,试想下如果l + 1 = r时,mid = (l + r) / 2 = l,一旦a[mid] <= x,l = mid = l,区间并没有缩小,从而陷入死循环;如果一开始取mid为r,一旦a[mid] <= x,l = mid = r,区间缩小,否则r = mid - 1 = l区间缩小,l都会与r相遇,就不会陷入死循环了。
如何做到上取整呢?只需要取mid时在l + r后面再加1即可,这里l和r都是闭区间,所以当a[mid] > x时,r = mid - 1.
是否还有其他办法既不修改区间的开闭性和循环终止条件,又不用上取整呢?答案是肯定的。

int l1 = l, r1 = n - 1;
while (l1 < r1) {
    int mid = l1 + r1 >> 1;
    if (a[mid] <= x)  l1 = mid + 1;
    else    r1 = mid - 1;
}
printf("%d %d\n", l, l1 - (a[l1] == x ? 0 : 1));
我们之所以会进行第二轮查找不大于x的最后一个位置,是因为第一轮已经找到了一个等于x的位置。所以完全可以当a[mid] <= x时,令l = mid + 1,此时,l指向的元素可能是x也可能比x大,但是由于不论大小,l和r的指针都移动了,就不会陷入死循环了,最后,如果a[l] == x则,l就是x出现的最后的位置,否则,l - 1就是x出现的最后一个位置。或许有人会疑惑,当a[mid] <= x时,l已经右移,最后l不是肯定指向的是大于x的位置嘛,为什么也可能指向等于x的位置?这是因为一旦第一轮查找的x出现的位置就是x唯一出现的位置,当x出现在数组末尾时,l == r,循环不会执行,此刻l指向的还是x,所以加上这个判断就可以解决该问题了。这也是二分程序可能遇见的第三种问题,当左右指针都移动时,待查找元素处在元素末尾会引起查找错误。

作者:昂昂累世士
链接:https://www.acwing.com/solution/content/3338/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

上一篇:L1-037 A除以B (10 分) 简单好懂


下一篇:leetcode--21--合并两个有序链表