二分的本质是边界。假设在一个区间上定义了某种性质,整个区间可以被一分为二,使得这个性质在右半段区间满足而在左半段不满足。二分可以寻找边界,既可以找到左半段的右边界a,也可以找到右半段的左边界b
l ab r xxxxxxxxxoooooooooooooooooooo 对于求两个边界,使用略微不同的模板。
模板一是找第一个满足条件的,
模板二是找最后一个满足条件的
bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用: int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; 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) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }//二分完之后l = r = 1
单调性有一定可以二分,没有不一定不可以,二分的本质不是单调性。