二分搜索不一定要求单调，只要数列可以被一个性质一分为二，分为左右两部分，就可以进行二分。

二分循环中的判断的条件为某个性质，如果想找满足这个性质的第一个数，当中点满足这个性质时，r = mid，不满足的话，l = mid + 1。

如果想找满足这个性质的最后一个数，当中点满足这个性质时，l = mid，不满足的话，r = mid - 1。同时计算中点时要加一 l + r + 1 >> 1。

  1. 循环条件为 l<r
  2. 出循环时 l == r，用哪个都行
  3. if 后面是 l=mid，前面求mid要+1进行上取整
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 判断重点是否满足某个性质
bool check(int mid) {
    ...
    return ...;
}

// 能二分的题一定是满足某种性质，分成左右两部分
// if的判断条件是让mid落在满足你想要结果的区间内

// 找满足某个条件的第一个数  即右半段
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;  
        else l = mid + 1;
    }
    return l;
}

// 找满足某个条件的最后一个数  即左半段
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        // +1 进行上取整
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}