二分

引例：一串连续的 $0$ 和一串连续的 $1$ 怎么找到第一个 $1$ ？
例如
0 0 0 1 1 1 1
1 2 3 4 5 6 7
显然可以用二分
以上面的例子举例
一开始 $l=1,r=7 ,mid=4$ .然而 $a[mid] = 1$ 。所以要移动右端点， $r=mid$ ，那么 $r$ 能等于 $mid-1$ 吗？
显然是不能的，如果 $mid$ 恰好是答案就错了！
接着 $l=1,r=4 ,mid = 2$ 然后 $a[mid]=0$。所以要移动左端点 , $l=mid+1$,因为 $a[mid]=0$,所以mid 不可能是第一个 $1$ ，所以 $l=mid+1$;
接着 $l=3,r=4 ,mid=3$,然后 $a[mid]=0$。同上
最后 $l=4,r=4 ,mid=4$ 然后停止。

---

思考一个问题这种做法的二分什么时候会停止？
显然是 $l>=r$ 的时候，所以当 $l=4,r=4$ 的时候循环就停止了。

那么最后的答案是什么呢？也就是第一个 $1$ 的位置应该在哪呢？就存放在最后的左端点里
在当前这个样例里恰好第一个 $1$ 就是 在 $l$ 这个位置。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
// 0001111
// 如果当前数为1 则返回 true
// 不然返回 false
bool check(int x)
{
    if(a[x] == 1)return true;
    return false;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> a[i];
    int l = 1, r = n;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid))r = mid;// 如果当前数为1则r=mid
        else l = mid + 1;// 不然 l=mid+1;
    }
    cout << l << '\n';
}

---

用同样的做法来看下一道二分答案的题
链接描述
同样的把问题抽象成 0000111 这样的问题
0 0 0 1 1 1 1
1 2 3 4 5 6 7
那么现在 $0$ 表示什么呢？表示当前的高度能够砍出 $M$ 长度的木材
那么 $1$ 表示什么呢？ 表示当前的高度不能砍出 $M$ 长度的木材
$so$ 如果按照这样的表示方法，最后的答案应该是什么呢？ 是 $L$ 吗
$L$ 表示的是第一个 $1$ ，但在这个题里要求是最后一个 $0$
那么最后一个 $0$ 就是 $L-1$
对于这类题目，跟前面题目不同的就是 check 函数里不同，二分的模板是一样的

#include<bits/stdc++.h>
using namespace std;
int a[1000005], n,m;
// 0001111
// 如果当前能砍的数的总数小于 M 则返回 true
// 不然返回 false
bool check(int x)
{
    long long sum = 0;
    for(int i = 1; i <= n; i++)
    {
        if(a[i] >= x)sum += a[i] - x;
    }
    if(sum < m)return true;
    return false;
}
int main()
{
    cin >> n>>m;
    for(int i = 1; i <= n; i++)cin >> a[i];
    int l = 1, r = 2e9;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid))r = mid;// 如果当前数为1则r=mid
        else l = mid + 1;// 不然 l=mid+1;
    }
    cout << l - 1 << '\n';
}

一般二分的题目只会输出第一 $1$ 或者是输出最后一个 $0$