二分总结

二分法一般应用在数组上, 在数组中以$O(\log{N})$的时间复杂度进行查找. 首先设置左右端点, 找到中间点, 一般根据(left + right) // 2找到中间点. 然后根据中间点的值与左右端点值的大小, 以及不同题目中各异的逻辑关系, 将其中的一个端点移动到中间点上或中间点附近, 完成一轮的迭代. 之后重复这个步骤, 直到满足停止条件, 这个条件一般是左右端点汇聚在一个位置时, 或左右端点越界, 左在右侧, 右在左侧, 这个条件也是要根据具体的题目确定. 最终左端点(普遍情况)或右端点所在的位置, 或这个位置对应的值就是最后的答案.

其中由很多细节:

• 端点移动的细节: 左右端点向中间移动时方案不同; 移动到中间点, 还是中间点邻近的一个位置

• 终止条件: 左右端点处于同一个端点时停止; 左右交叉后停止

• 前两者的结合, 终止条件的变化, 很可能就会导致移动细节的变化

• 其他

中点与移动

一般求新的中点使用公式(left + right) // 2. 由于使用的是整除, 所以存在 $\text{left} \le \text{mid} \lt \text{right}$, 即如果left和right不相等, 得到的mid是一定小于右端索引, 不小于左端索引, 但是可能与左端相等, 即mid就是left.

这点非常重要. 因为我们设计移动策略的时候, 要保证端点不能原地移动, 否则左右端点经过一轮迭代后没有移动, 求出的中间点还是一样的, 会陷入死循环.

所以在制定左侧端点的移动策略时, 一般在满足特定条件后需要移动左端点时, 会使left = mid + 1, 以避免最终原地踏步, 陷入死循环. 而右侧端点使得right = mid即可.

当然能否这样移动, 不同题目还需要进行不同的考虑.

终止条件

如果是左右端点处于同一个端点时停止, 则循环条件应写为while left < right; 如果是左右交叉后停止, 循环条件应写为while left <= right. 在实际题目中设置终止条件时, 可以多考虑以下点.

如何到达left == right

按照left = mid + 1和right = mid的移动策略, 一轮迭代之后, 满足left == right, 有两种情况.

移动右结点

要求迭代前left与right相邻, 即left = right - 1, 两者确定的子数组长度为2. mid = (left + right) // 2 = left, 两者相遇.

移动左节点

根据mid = (left + right) // 2 + 1 = right, 可以得到此时left = right - 2, 两者确定的子数组长度为3.

实例演示

参考[704][中等][二分] 二分查找.