二分法的适用场景
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才能平衡。