uli's blog

/主页

/文章

/朋友

/关于

Home > Posts > 彻底解决二分边界问题

彻底解决二分边界问题

从搜索区间入手

(Modified: )   ·   2 min read

本文假设读者已理解并会写二分算法，因此聚焦于解决边界问题。

希望本文能够帮助你学会设计二分算法的方法，写出自信能够正常运行的二分代码。

前言

二分作为最 useful 的经典算法，可以说是所有计算机学生必会的算法之一。然而，边界问题却总是令人破防：

  1. 答案是 left 还是 right？
  2. mid 到底应该等于 (left + right)/2 还是 (left + right + 1)/2？
  3. 收缩区间时 left 和 right 到底等于 mid，还是 mid - 1，mid + 1？
  4. while 的条件到底是 left < right 还是 left <= right？

诸如此类问题导致了我们写的二分往往不能符合预期，得不到预期的答案，甚至老是死循环。一种解决方式是尝试，把所有写法全试一遍。另一种解决方式是背模版，将各种可能的写法全背下来。但我们都没有真正解决问题，即真正会写二分。其实，二分的边界问题并不复杂，也并不需要一堆证明和讨论，只要我们掌握了正确的思考方式，即从搜索区间入手。

解析

基本定义

让我们先抛弃对二分已有的混乱认识。最基本的，二分是要在一堆 尚待确定 的元素里找到我们需要的那个，并且它们满足某种性质，让我们每次都可以排除掉一半。由于元素往往是以顺序表的形式存储，所以我们可以将搜索空间定义为 搜索区间，将搜索区间中的元素定义为 候选元素。

接下来，让我们看一段常见的二分代码：

while(left <= right){
    int mid = (left + right) / 2;
    if (check(mid)) left = mid + 1;
    else right = mid - 1;
}

一共 5 行代码，可以拆解为三步：

  1. 当搜索区间不为空，循环执行下面步骤
  2. 找出一个基准元素 mid，将区间划分为左右两部分
  3. 根据 mid 是否满足条件，缩小搜索区间

下面，我们就从这三步入手，看看代码到底该怎么写。

定义搜索区间

最常见的定义方式有两种：闭区间 [left, right] 和 左闭右开区间 [left, right)。在闭区间下，left 是第一个候选元素，right 是最后一个候选元素；在左闭右开区间下，left 同样是第一个候选元素，但 right 是 最后一个候选元素的下一个元素。

由此定义，易得循环条件：

  1. 闭区间：当 left <= right，搜索区间就不为空。循环结束时，left = right + 1，right 是最后一个候选元素，left 是 最后一个候选元素的下一个元素。
  2. 左闭右开区间：当 left < right，搜索区间就不为空。循环结束时，left = right，left 和 right 都是 最后一个候选元素的下一个元素。

记得定义完区间后，给 left 和 right 赋初值就需要满足定义。

缩小搜索区间

由于候选元素存在二分性质，答案只会存在于左半边或右半边，我们要通过调整 left 或 right 来缩小搜索区间。这里有两个原则：

  1. 保证搜索区间缩小（否则会死循环）
  2. 保证缩小后的区间仍满足定义（否则无法保证随后的循环中使用相同的缩小策略是正确的）

让我们分两种情况来看：

  1. 答案在左半边（mid 不满足条件）：此时应该舍弃右半边，即移动 right。如果区间定义为闭区间，那么 mid 显然不应该包含在缩小后的区间中，right = mid - 1。如果区间定义为左闭右开区间，那么 right 应该等于 最后一个候选元素的下一个元素，即 mid。

  2. 答案在右半边(mid 满足条件)：此时应该舍弃左半边，即移动 left。这种情况下，无论使用哪种定义，都有 left = mid + 1。

    这里，你可能会问：mid 是满足条件的，为什么要把它丢掉？查看上面关于候选元素的定义：搜索区间中 尚待确定 的元素。mid 已经被确定，所以不能包含在缩小后的搜索区间中。

    另一个问题是：如果 mid 是最终的答案，它会不会被丢掉？由于左闭右开区间下，最后的结果是 left 和 right 都是 最后一个候选元素的下一个元素，那么 mid 作为答案被丢弃也是正常的事情。我们可以保证 left 和 right 最终会收敛到 mid + 1，读者可以结合下面的代码思考。

由此，我们已经能够写出左闭右开定义版本的二分：

while(left < right){
    int mid = (left + right) / 2;
    if (check(mid)) left = mid + 1;
    else right = mid;
}

在我们的定义下，mid 无论如何都会被舍弃。事实上，并不是所有二分都必须把 mid 丢弃，我们这里采用的定义能够让我们使用统一的定义和写法来避免错误。如果我们在移动 left 的时候保留 mid，为了保证区间一定缩小，在找 mid 的时候就需要“偏置”。如果写成 left = mid，那么 mid 必须偏右，常见实现是向上取整 mid = (left + right + 1)/2。

返回结果

最后，我们要的答案是谁？基于上面的讨论，不难得出：

  1. 如果我们需要最后一个满足条件的元素：
    1. 闭区间返回 right 或者 left - 1
    2. 左闭右开区间返回 left - 1 或者 right - 1
  2. 如果我们需要第一个满足条件的元素，那么我们应该修改条件，例如我们要找第一个大于等于 target 的元素，就等价于找到最后一个小于 target 的元素的下一个元素，将问题转化为上一种情况

此外，还存在一种在二分过程中记录答案的写法：

int ans = 0;
while (left <= right)
{
    int mid = (left + right) / 2;
    if (check(mid))
    {
        ans = mid;
        right = mid - 1;
    }
    else left = mid + 1;
}

区间的收缩方式与我们上面讨论的并无差别，不同在于增加了一个 ans 变量记录中间结果。这种写法的思路是：已知 mid 是一个满足条件的答案，我们将其保留，如果遇到更好的答案就进行替换。

我们上面的写法是基于分界的思想，通过调整二分条件让区间收敛到所需要的答案。而这里的写法不依赖收敛点，而是不断更新最优答案。看起来这种写法具有更强的泛用性，也因此被很多人喜爱，但它无法替代我们上面对于搜索区间的思考。

总结

其实，只要搜索区间的定义决定了，那么二分的写法就是唯一确定的，因为我们要在整个过程中保持搜索区间的定义不变，这样它才能按照固定的方式缩小。

推荐现在就去完成这道力扣题目：34. 在排序数组中查找元素的第一个和最后一个位置，按照上文所述的思考方式，相信你可以一发 AC。

←
终极家庭组网指南
back to top