二分法的适用场景

1. 有单调性的题目一定可以二分

2. 没有单调性也有可能二分

由此可见，二分的核心并不是单调性。

核心是：定义了某种性质，使得可以将整个数据集一分为二，左半边满足一种性质，右半边不满足；右半边满足另一种性质，左半边不满足。则二分可以寻找左区间的边界，也可以寻找右区间的边界。

二分法的边界问题非常重要，稍不注意就可能会死循环。

二分法有两个模板，两个模板最核心的区别是：取中点时，mid = (l + r) / 2  or  mid = (l + r + 1) / 2  

两个模板

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用
int bsearch_1(int l, int r) {
    // 由于区间的划分对右区间不利，因此mid要稍微取小一些
    while(l < r) {
        int mid = l + r / 2;
        if(check(mid)) r = mid  // check()判断mid是否满足性质
        else l = mid + 1;
    }
　　 return l;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
int bsearch_2(int l, int r) {
    while(l < r) {
        // 由于区间的划分对左区间不利，因此mid要稍微取大一些
        int mid = (l + r + 1) / 2; 
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

两个模板的选择问题

1. 如果求左区间的终点（mid属于左区间，即区间划分方式为[l, mid]和[mid + 1, r]），第二个模板

2. 如果求右区间的起点（mid属于右区间，即区间划分方式为[l, mid - 1]和[mid, r]），第一个模板

苦难点在于mid = (l + r) / 2  or  mid = (l + r + 1) / 2  的选择。

技巧

难点在于mid是否+1.首先先不用管mid，而是确定是取左半边的区间终点还是右半边的起点。如果是左半边，那么l = mid, or r = mid - 1，如果出现了mid-1，说明左区间在区分划分上吃亏了，那么我们需要尽可能的将mid大一些，如此才能平衡左区间的吃亏。因此，mid=(l+r+1)/2.
否则，如果是取右半边的区间起点，那么r = mid, l = mid + 1,如此左区间沾光有区间吃亏，因此需要让mid取得稍微左一些即(l+r)/2才能平衡。