本质
在有序区间内，找到一个分界线，分界线左侧元素均不满足某一个性质，右侧则相反。
极端情况下，左边和右边都可能为空。
可以按照具体定义将分界线归属为左边或者右边。
比如，上面的分界线 0 左侧都不大于 0，右侧都大于 0。
先决条件
- 区间内元素有序；
- 区间左右端点确定。
题目特点
求某个最优解——比如，最小值最大、最大值最小。
最优解也就是分界线，左半边的右边界或者右半边的左边界。
比如，方程式求根，本质就是求区间内求满足 \(f(x)\leqslant 0\) 的 \(f(x)\) 的最小值(也就是 \(0\)) 对应的 \(x\)；或者，像是如何使得玩家受到的伤害最小。
题目模板
- 定义左右端点
- 是否已经找到目标边界线（目标元素）——左右端点表示的区间只有一个元素时
- 计算中间点
- 判断中间点是否满足条件——
while(condition)
4.1 如果满足尝试在中间点左侧进行查找——将当前中间点作为右端点。
4.2 否则，在中间点右侧进行查找——将当前中间点作为左端点。
4.3 回到 2
left = ...;
right = ...;
while (left < right)
{
mid = ...;
if (pred(mid))
{
right = mid;
}
else
{
left = mid;
}
}
开区间和闭区间
开区间对应 [left, right)，这时候右端点不可能是目标边界线。所以为了确保区间不为空，必须满足 while(left < right)，我们为了确保循环结束后区间对应一个元素应该将 while 中的条件设置为 left + 1 < right，这样循环结束时就会满足 left + 1 = right 的条件了。
闭区间对应 [left, right]，右端点也可能是目标边界线。所以为了确保区间不为空，必须满足 while(left <= right)，我们为了确保循环结束后区间对应一个元素应该将 while 中的条件设置为 left < right，这样循环结束时就会满足 left = right 的条件了。
中间点 mid 的计算
如果区间内只包含两个元素时，中间点 mid 会等于左端点或者右端点。
为了避免的死循环的问题，我们需要确保每次循环之后，区间范围都会减少——也就是左右端点中的某一个都会向中间移动一些。这时候，如果 mid 会等于左端点或者右端点，我们再让这个端点等于 mid，就会使用区间范围永远不变——陷入了死循环。这时候，我们应该让 left = mid + 1 或者 right = mid - 1。
左右端点的更新方法和 mid 计算方法的对应关系如下。
mid = (left + right) / 2; // mid 靠左, 注意溢出的问题
left = mid + 1;
right = mid;
mid = (left + right + 1) / 2; // mid 靠右, 注意溢出的问题
left = mid;
right = mid - 1;
防止加法溢出的技巧
可以将
mid = (left + right) / 2;
替换为
mid = left + (right - left)/2;
或者将
mid = (left + right + 1) / 2;
替换成
mid = left + (right - left)/2 + ((left ^ right) & 1); // left 和 right 为一奇一偶时，需要 + 1