1.答案有确定的范围（时间复杂度一般近似O[lg(right-left+1)]；
2. 问题的答案是单调的
注意: check验证函数的编写是二分答案的核心。出不出错就看它了
查找值的时候, 记得中间等于号的使用:
理解至上:
当mid = l + r + 1 , 取到的值是偏右的, l没有问题, 后面r = 得偏回来, 不满足条件就不加这个边界, r = mid - 1
当mid = l + r , 取到的值是偏左的, r没有问题, 后面l = 得偏回来, 不满足条件就不加这个边界, l = mid + 1
//比如:
mid = l + r + 1>> 1; if(mid >= n) l = mid;
else r = mid - 1;
//----------------------
mid = l + r >> 1; if(mid >= n) r = mid; else l = mid + 1;
模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质 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; }
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; }
原文：https://www.cnblogs.com/la-la-wanf/p/14590111.html