二分算法

二分算法也是面试必备的算法，主要维护具有单调性质的序列，经常被迁移到知识点有中位数。。。

//二分值偏大
while(l!=r)
    {
        int mid=(l+r)/2+1;
        if(nums[mid]<=target)
              l=mid;
        else
              r=mid-1;
}


//二分值偏小
 while(l!=r)
    {
        int mid=(l+r)/2;
        if(nums[mid]>=target)
              r=mid;
        else
              l=mid+1;
}

这个版蛮好用的，基本不会出错，二分算法的题目基本可以转化为具有单调性质的模型。

1.Burning Midnight Oil http://codeforces.com/contest/165/problem/B
典型的一道二分题，具有单调性，维护最小值，那么就用二分值偏小的版吧
code:http://codeforces.com/contest/165/submission/45203439

2.Frodo and pillows http://codeforces.com/contest/760/problem/B
也具有单调性，我们维护的数尽可能大，所以检测的数的最小值满足要求就可以了，然后用二分值偏大的版吧
code:http://codeforces.com/contest/760/submission/45231233
补一下吧，二分的做法还是要从例子中先画出单调曲线，来做，我们以leetcode275题为例子

图片.png
找到单调线
被引用的次数h 0 1 2 3 4 5 6

=h引用的篇数s 5 4 3 3 2 2 1
然后h-s就是单调的，为 -5 -3 -1 0 2 3 5
并且我们二分被引用的次数h，统计大于等于h的篇数s，然后说取大的，那就用偏大的模板。
https://leetcode-cn.com/submissions/detail/22733530/