浅谈二分与二分答案

前言

二分是个看似很简单的算法其实它的思想非常的巧妙
此外二分中有很多细节也是值得思考的

下面也讲讲我个人对二分的理解吧

我们就先拿一个简单的例子好了寻找单调递增序列(arr)中位置最靠左且(geq x)的数
在这里我先随便给个序列吧

1 1 2 3 6 7 9 9
x = 5

显然答案是(arr_4=6)
在这里我们可以把原序列转化我们定义(geq x)为一个条件将序列中所有数分为满足条件和不满足条件
我们定义一个函数(f(x)) 这个函数的返回值只有可能是0或1
如果(arr_igeq x) 即(arr_i)满足条件那么(f(i)=1)
否则(f(i)=0)

arr  1 1 2 3 6 7 9 9
f(x) 0 0 0 0 1 1 1 1

我们要寻找下标最小的满足条件的数
问题就被转化成了寻找最左边的1
其实原序列即使是个不单调的也无所谓只要我们最后转化成的01序列是单调的就可以进行二分

如果序列是单调递减的要找最右边的满足(geq x)的数:

arr  9 9 7 6 3 2 1 1
f(x) 1 1 1 1 0 0 0 0

我们要找到最右边的1的位置
我们可以把它看作最左边的0的位置减1 显然这是对的
注意全是0的情况

当然我们有时候也会去找最大/最小的不符合条件的数本质都比较相似
这个条件是我们根据题目自己定义的只要满足这个条件下(f(x))具有单调性这个条件怎么选都是可以的

所有的二分问题就可以被转化成这样的形式

eg:查找一个单调序列中 (x) 出现了多少次
两次二分条件分别是(geq x)和(>x)

arr  1 1 2 4 5 5 5 6 7 7 8
f(x) 0 0 0 0 1 1 1 1 1 1 1
            i^
g(x) 0 0 0 0 0 0 0 1 1 1 1
                  j^

两个都找最左边的1 (j-i)就是答案

拿这题举例子
把条件设为"每段和的最大值(leq x)"
能满足则(f(x)=1) 不能则(f(x)=0)
对于样例得到这样一个序列

x    1 2 3 4 5 6 7 8 9
f(x) 0 0 0 0 0 1 1 1 1

f(x)的计算方式很简单...这里就略过了
找到最左边的1 它就是答案

二分答案通过这种方式把一个最优化问题转化成判断可行性问题
单调性是前提

很关键
我的二分一般都是这么写的
假设在这样一个序列上做二分

x    1 2 3 4 5 6 7 8 ... n
f(x) 0 0 0 0 1 1 1 1 ... 1

代码:

while(l <= r){
	mid = (l + r) >> 1; // (l+r)/2
    if(f(mid) == 1) r = mid - 1;
    else l = mid + 1;
}
// l是答案

如果mid=1 那么([mid,n])一定都是1
如果mid=0 那么([1,mid])一定都是0
这样的话一定要做到(l>r)
因为在这样的情况下

0 0 0 ? 1 1 1 1
     l^r

由于l = mid + 1和r = mid - 1 l和r所在位置并没有被判断过是0或者是1 这里也要判断

有时候我们要找最右边的0 直接把l-1就可以了

如果序列是这样的

x    1 2 3 4 5 6 7 8 ... n
f(x) 1 1 1 1 0 0 0 0 ... 0

就照常写

while(l <= r){
	mid = (l + r) >> 1; // (l+r)/2
    if(f(mid) == 0) r = mid - 1;
    else l = mid + 1;
}
// l是答案

找到最左边的0
找最右边的1就把l-1

还有一种写法比较保险一点就是在每次查找到(f(x))的值符合你想要的值的时候记录ans=mid 最后ans是答案

while(l <= r){
	mid = (l + r) >> 1; // (l+r)/2
    if(f(mid) == 1){
    	ans = mid;
        r = mid - 1;
    }
    else l = mid + 1;
}
// ans是答案