NeverKnowsTomorrow
0%

用循环不变式理解并写出正确的二分查找算法

发表于 更新于 阅读次数： Valine：
本文字数： 8.3k 阅读时长 ≈ 8 分钟

本文参考自 如何写出正确的二分查找？—— 利用循环不变式理解二分查找及其变体的正确性以及构造方式 一文，改进了原文的描述，修改了部分代码。

序言

本文以经典的二分查找为例，介绍如何使用 循环不变式 来理解算法，并利用循环不变式在原始算法的基础上根据需要产生算法的变体。谨以本文献给在理解算法思路时没有头绪而又不甘心于死记硬背的人。

二分查找究竟有多重要？《编程之美》第 2.16 节的最长递增子序列算法，如果想实现 $O (n^2)$ 到 $O (n \log n)$ 的时间复杂度下降，必须借助于二分算法的变形。其实很多算法都是这样，如果出现了在有序序列中元素的查找，使用二分查找总能比线性查找算法拥有更好的性能。

然而，虽然很多人觉得二分查找简单，但随手写一写却不能得到正确的结果：死循环、边界条件等等问题伴随着出现。《编程珠玑》第四章提到：提供充足的时间，仅有约 10% 的专业程序员能够完成一个正确的二分查找。当然，正确的二分查找和变体在算法书籍以及网络上随处可得，但是如果不加以理解，如何掌握？理解时，又往往因想不清楚，一知半解，效果有限。我在看相关的变体算法时就觉得一片茫然，不得要领：或许这个算法可以这么写，稍微变下要求就不能这么写了；举正例说明算法在某些情况下可以正常工作、举反例说明算法有错固然可行，但仅有例子是不够的，怎样一劳永逸地证明自己几经修改的算法之正确？如果每一个变体都进行孤立地理解，那么太花费时间，而且效果也不好。如何解决这个问题？在思考方法和查阅书籍之后发现，还是要靠循环不变式来完成算法正确性的理论支撑。

或许你曾了解过循环不变式，但如果不使用的话，是看不到它的强大之处的：不仅仅能帮助你证明算法正确性，同时也帮助你理解算法，甚至能帮助你在基本算法的基础上，构造出符合要求的相应算法变体。这些都将在后文的各个算法说明中看到。

知识准备

结合《算法导论》和《编程珠玑》，下面说明循环不变式的概念与性质。

循环不变式（loop invariants）主要用来帮助理解算法的正确性。实际上它不只是一种计算机科学的思想，准确地说是一种数学思想。在数学上阐述了通过循环（迭代、递归）去计算一个累计的目标值的正确性，属于基础数学的范畴，而且在计算机上也应用广泛。

循环不变式主体是不变式，也就是一种描述规则的表达式。其过程分三个部分：初始，保持，终止。　

  1. 初始：保证在初始的时候不变式为真。
  2. 保持：保证在每次循环开始和结束的时候不变式都为真。
  3. 终止：如果程序可以在某种条件下终止，那么在终止的时候，就可以得到自己想要的正确结果。

下面我们列举二分查找的几个经典问题，来理解循环不变式的在判断算法正确性中的应用。

例题

二分查找的前提是数组有序，这里我们假设有一个有序数组 nums [n]，元素从小到大排列，要查找的元素为 key，算法用 Java 描述。

1. 二分查找值为 key 的下标 x，如果不存在返回 -1。

循环不变式

如果 key 存在于原始数组 nums [n] 中，那么要查找的元素下标 x 一定在 [left, right] 中。

初始化

第一轮循环开始之前，处理的数组就是原始数组，这显然成立。

保持

每次循环开始前，key 存在于待处理的数组 nums [left] ~ nums [right] 中。我们先暂定一个循环条件 left <= right，违反则意味着 x 不存在。写下 nums [mid] 与 key 的比较判断分支：

  1. 对于 nums [mid] < key，nums [left] ~ nums [mid] 均小于 key，key 只可能存在于 nums [mid + 1] ~ nums [right] 中，故舍弃 nums [left] ~ nums [mid]，数组减少的长度为 mid - left + 1；

  2. 对于 nums [mid] > key，nums [mid] ~ nums [right] 均大于 key，key 只可能存在于 nums [left] ~ nums [mid - 1] 中，故舍弃 nums [mid] ~ nums [right]，数组减少的长度为 right - mid + 1；

  3. 对于 nums [mid] == key，则查找到了 key 的下标，直接返回 mid。

因为 left <= mid <= right，在前两种情况下，数组长度每次至少减少 1，迭代过程不会发生死循环。

终止

结束时，left > right，待处理数组为空，表示 key 不存在所有步骤的待处理数组中，再结合每一步排除的部分数组中也不可能有 key，因此 key 不存在于原数组。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class BinarySearch {
    int binarySearch(int[] nums, int key ) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums [mid] == key) {
                return mid;
            } else if (nums [mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

2. 二分查找返回 key（可能有重复）第一次出现的下标 x，如果不存在返回 -1

循环不定式

如果 key 存在于数组，那么 key 第一次出现的下标 x 一定在 [left, right] 中，且有 nums [left] <= key <= nums [right]。

初始化

第一轮循环开始之前，处理的数组是原数组，这时显然成立。

保持

每次循环开始前，如果 key 存在于原数组，那么下标 x 存在于 [left, right] 中。同样暂定循环条件为 left <= right，写下 nums [mid] 与 key 的比较判断分支：

  1. 对于 nums [mid] < key，nums [left] ~ nums [mid] 均小于 key，key 只可能存在于 nums [mid + 1] ~ nums [right] 中，故舍弃 nums [left] ~ nums [mid]，数组减少的长度为 mid - left + 1，至少为 1；

  2. 对于 nums [mid] >= key，则 nums [mid] 是 nums [mid] ~ nums [right] 中第一个大于等于 key 的元素，后续的等于 key 的元素（如果有）不可能对应于下标 x，故舍去 nums [mid + 1] ~ nums [right]，此时 x 应在 [left, mid] 中，数组的减少长度为 right - (mid + 1) + 1，即 right - mid。当 right == mid，即 left == right 时，每次减少的数组长度变成 0，将陷入死循环，为了避免这种情况，应调整循环条件为 left < right；

终止

此时 left >= right，在每次循环结束时，left 总是 x 第一个可能的下标，nums [right] 总是第一个等于或者大于 key 的元素。

那么对应于 left == right 的情况，检查 nums [left] 即可获得 key 是否存在，若存在则下标为 x；

对于 left > right 的情况，其实是不用考虑的。因为此时因不满足循环条件，在 left == right 时，已经结束了循环，这一轮的循环不可能进入。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class BinarySearchFirst {
    int findFirstKey(int[] nums, int key) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums [mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums [left] == key) {
            return left;
        }
        return -1;
    }
}

3. 二分查找返回 key（可能有重复）最后一次出现的下标 x，如果不存在返回 -1（模仿 2 的第一版）

循环不定式

如果 key 存在于数组，那么 key 最后一次出现的下标 x 一定在 [left, right] 中，且有 nums [left] <= key， nums [right] >= key。

初始化

第一轮循环开始之前，处理的数组是原数组，这时显然成立。

保持

每次循环开始前，如果 key 存在于原数组，那么下标 x 存在于 [left, right] 中。同样暂定循环条件为 left <= right，写下 nums [mid] 与 key 的比较判断分支：

  1. 对于 nums [mid] < key，nums [left] ~ nums [mid] 均小于 key，x 只可能存在于 nums [mid + 1] ~ nums [right] 中，舍去 nums [left] ~ nums [mid]，数组减少长度为 mid - left + 1，至少为 1；

  2. 对于 nums [mid] == key，nums [mid] 是 nums [left] ~ nums [mid] 中最后一个值为 key 的元素，那么下标 x 的候选只能在 [mid, right] 中，舍去数组 nums [left] ~ nums [mid - 1]，减少长度 (mid - 1) - left + 1，即 mid - left。当循环条件满足 left == right 或 left == right - 1 时，此时 mid == left，数组减少长度变成 0，如果不进行干预将陷入死循环，我们加入判断分支即可解决。这时，剩下的数组元素个数可能是 1，也可能是 2，当为 2 时，优先判断 nums [right] 是否等于 key，等于就直接返回 right，否则返回 left；

  3. 对于 nums [mid] > key，nums [mid] ~ nums [right] 均大于 key，x 只可能在 [left, mid - 1] 中，舍去 nums [mid] ~ nums [right]，数组减少长度为 right - mid + 1，至少为 1；

终止

此时 left > right，数组中没有符合要求的元素，直接返回 -1。

说明

与上一种不同，这个算法不能简单地根据对称，从上一个算法直接改过来，由于整数除法总是舍弃小数，mid 有时会离 left 更近一些。所以这种算法只是沿着上一个算法思路的改进，看上去并不是很漂亮。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class BinarySearchLast {
    int findLastKey(int[] nums, int key) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums [mid] < key) {
                left = mid + 1;
            } else if (nums [mid] == key) {
                if (left == mid) {
                    if (nums [right] == key) {
                        return right;
                    } else {
                        return left;
                    }
                } else {
                    left = mid;
                }
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

4. 二分查找返回 key（可能有重复）最后一次出现的下标 x，如果不存在返回 -1（修改版）

根据 3 中的讨论，可以发现不能直接照搬的原因是 mid = (left + right) / 2 会舍弃小数，在 left + 1 == right 且 nums [left] = key 时，如果不加以人为干预会导致死循环。既然最终需要干预，干脆把需要干预的时机设置为终止条件就行了。

循环条件设置为 left < right - 1 就可以保证每次循环时数组长度都会至少减 1，不会进入死循环。

同上所述，对于 nums [mid] < key，x 只可能存在于 nums [mid + 1] ~ nums [right] 中，故令 left = mid + 1，对于 nums [mid] == key，x 只可能存在于 nums [mid] ~ nums [right] 中，故令 left = mid。

两者情况实际上可以结合在一起，nums [mid] < key 时，令 left = mid 也是满足条件的，所以对于 nums [mid] <= key，令 left = mid 是可行的。

对于 nums [mid] > key，同 3 中描述。

终止

此时，数组长度可能为 2，也可能为 1。因为 right 总是指向数组中候选的最后一个可能为 key 的下标，所以优先判断 nums [right] 是否等于 key，等于就直接返回 right，否则判断 nums [left] 是否等于 key ，是则返回 left；

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class BinarySearchLast {
    int findLastKey(int[] nums, int key) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right - 1) {
            mid = left + (right - left) / 2;
            if (nums [mid] <= key) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (nums [right] == key) {
            return right;
        } else if (nums [left] == key) {
            return left;
        }
        return -1;
    }
}

5. 二分查找返回刚好小于 key 的元素下标 x，如果不存在返回 -1

如果第一反应是通过 2 的方法找出第一个为 key 的元素，返回它的下标减 1，那么就错了：这个二分查找并没有要求 key 本身在数组中。

循环不变式

如果原始数组中存在比 key 小的元素，那么原始数组中符合要求的元素存在于待处理的数组。

初始化

第一轮循环开始之前，处理的数组是 nums [0] ~ nums [n - 1]，这时显然成立。

保持

每次循环开始前，下标 x 存在于 [left, right] 中。

暂定循环条件为 left <= right，违反则意味着 x 不存在，写下 nums [mid] 与 key 的比较判断分支：

  1. 对于 nums [mid] < key，nums [left] ~ nums [mid] 均小于 key，x 只可能在 [mid, right] 之间，舍去 nums [left] ~ nums [mid - 1]，数组减少长度为 (mid - 1) - left + 1，即 mid - left。当 left == right 或 left == right - 1 时，mid == left， 数组减少长度变成 0，将陷入死循环。所以我们将循环条件调整为 left < right - 1；
  2. 对于 nums [mid] >= key，nums [mid] ~ nums [right] 均大于等于 key，x 只可能在 [left, mid - 1] 之间，舍去 nums [mid] ~ nums [right]，数组减少长度为 right - mid + 1，至少为 1；

终止

接着保持中的讨论，结束时，符合的元素要么在最终的数组中，要么既不在最终的数组中也不在原始的数组中（因为每一次循环都是剔除不符合要求的元素）。

同样，数组长度为 2 时，right == left + 1，此时先检查 nums [right] 是否小于 key，后检查 nums [left]，符合要求就返回下标。两者都不符合则返回 -1。数组长度为 1 时，只用检查一次 nums [right] 即可。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class BinarySearchSmall {
    int findSmall(int[] nums, int key) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right - 1) {
            mid = left + (right - left) / 2;
            if (nums [mid] < key) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (nums [right] < key) {
            return right;
        } else if (nums [left] < key) {
            return left;
        }
        return -1;
    }
}

6. 二分查找返回刚好大于 key 的元素下标 x，如果不存在返回 -1

循环不变式

如果原始数组中存在比 key 大的元素，那么原始数组中符合要求的元素对应下标 x 存在于待处理的数组。

初始化

第一轮循环开始之前，处理的数组是 nums [0] ~ nums [n - 1]，这时显然成立。

保持

每次循环开始前，下标 x 存在于 [left, right] 中。

暂定循环条件为 left <= right，写下 nums [mid] 与 key 的比较判断分支：

  1. 对于 nums [mid] <= key，nums [left] ~ nums [mid] 均小于等于 key，x 只可能存在于 [mid + 1, right] 中，舍去 nums [left] ~ nums [mid]，数组减少长度为 mid - left + 1，至少为 1；
  2. 对于 nums [mid] > key，nums [mid] ~ nums [right] 均大于 key，x 只可能存在于 [left, mid] 中，舍去 nums [mid + 1] ~ nums [right]，数组减少长度为 right - (mid + 1) + 1，即 right- mid。当 left == right 时，right == mid，数组减少长度变成 0，将陷入死循环，所以把循环条件调整为 left < right；

终止

此时 left == right，只要检查 nums [left] 是否大于 key 即可。

补充说明

如果题目是对数组进行动态维护，返回值 - 1 可以改为 left + 1，表示下一个需要填入元素的位置。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class BinarySearchBig {
    int findBig(int[] nums, int key) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if(nums [mid] <= key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums [left] > key) {
            return left;
        }
        return -1;
    }
}

总结：如何写出正确的二分查找代码？

结合以上各个算法，可以找出根据需要写二分查找的规律和具体步骤，比死记硬背要强不少，万变不离其宗嘛：

  1. 前提是有序数组，框架是二分，那么循环的 key 与 nums [mid] 的比较必不可少，这是基本框架；
  2. 循环的条件可以先写一个粗略的，比如原始的 while (left <= right) 就行，这个循环条件在后面可能需要修改；
  3. 确定每次二分的过程，要保证所求的元素必然不在被排除的元素中，换句话说，所求的元素要么在保留的其余元素中，要么可能从一开始就不存在于原始的元素中；
  4. 检查每次排除是否会导致保留的候选元素个数的减少？如果没有，分析这个边界条件，如果它能导致循环的结束，那么没有问题；否则，就会陷入死循环。为了避免死循环，需要修改循环条件，使这些情况能够终结。新的循环条件可能有多种选择：while (left < right)、while (left < right - 1) 等等，这些循环条件的变种同时意味着循环终止时候选数组的形态；
  5. 结合新的循环条件，分析终止时候选元素的形态，检查要查找的元素是否在其中；
  6. 对于 3，有一些二分算法实现不是这样的，它会使 left 或 right 在最后一次循环时越界，相应的 left 或 right 是查找的目标的最终候选，这一点在理解时需要注意。当然，不利用这个思路也可以写出能完成功能的二分查找，而且易于理解。

进阶

查找排序数组中某个数出现的次数。(《剑指 Offer》面试题 38，2013.7.18 更新）

解法：二分查找确定第一次和最后一次出现的下标，差值 +1 就是出现次数，时间复杂度 $O (\log n)$.

参考资料

如何写出正确的二分查找？—— 利用循环不变式理解二分查找及其变体的正确性以及构造方式