程序员面试题精解（3）— 二分查找

发表于 更新于 分类于 阅读次数： 本文字数： 15k 阅读时长 ≈ 13 分钟

正如“算法分析之父”高德纳所言：尽管二分查找的基本思想相对简单，但细节可能出乎意料地棘手。在实际面试中，有非常多的程序员无法写出正确无误的二分查找程序。

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky.
— Donald Knuth（高德纳，著名计算机科学家，现代计算机科学的先驱人物，名著《计算机程序设计艺术》的作者，1974年图灵奖得主）

基本算法

二分查找，也称二分搜索或折半搜索，是一种在有序数组中查找给定元素的搜索算法。它的基本思想是：从数组的中间元素开始与目标值其进行比较，如果相等则搜索过程结束；否则，排除目标值不在其中的那一半，继续在余下的一半内查找，再次取中间元素与目标值进行比较，反复进行直到找到目标值；如果某一步骤时余下的数组为空，则表明给定元素代表不在数组中。二分查找算法的时间复杂度是 \(O(\log n)\)，是很有效率的搜索算法。

可惜的是，仅仅了解二分查找的算法思想并不能保证你可以写出准确无误的程序。美国计算机科学家乔恩·本特利（Jon Bentley）在他的计算机科学经典名著《编程珠玑》中提到，在给专业程序员的培训课程中布置二分查找作业，90%的人在数小时后仍然未能提供正确的答案。

二分查找思路虽然简单，但是从各种要求和条件中产生的差异常常令人难以招架。这里我们借助契约编程的理念，解析二分查找的解法框架和两种基本算法实现，目标就是要将细节中魔⿁关在笼子里。

契约编程

要编写出二分查找正确实现，首先要掌握契约编程的概念。契约编程是一种计算机软件设计的方法。这种方法要求软件设计者为程序组件定义正式的、精确的并且可验证的接口。具体到二分查找函数的这样模块，就包括先决条件（precondition)、后置条件（postcondition）、循环不变式（loop invariant）和限定函数（bound function）这些关键要素。它们的解释如下

  • 先决条件：函数调用之前必须成立的条件。如果先决条件被违反了，则代码将产生未定义行为，其运行的结果将偏离设计目标。不正确的先决条件还可能引发安全问题。
  • 后置条件：指在执行一段代码后必须成立的条件，其正确性由函数在终止执行时保证。简单的说，后置条件就是函数对其输出结果的承诺。
  • 循环不变式：指在循环开始和循环中，每一次迭代时为真的性质，也是在循环开始和结束后始终成立的条件。
  • 限定函数：定义为仍需执行的迭代次数的上限。可以把它看作是一个表达式，其值随着循环的进行而单调地减少。当它达到或小于零时，循环结束。

对于二分查找函数，显然输入必须是有序数组，这是常常被忽视的先决条件。函数的后置条件就是清晰定义的搜索结果。如果给定元素在数组中，就返回其索引（或指针）值，不然就输出预先定义的表示不存在的数值。此数值不应该与数组的索引值混淆。二分查找的循环不变式要求“如果目标值存在于数组中，那么目标值就一定存在于当前的搜索区间内”，这是正确代码实现的最重要的要素。如果这条不能总成立，那么函数必然出错！最后的限定函数由当前区间决定，因为每次的搜索空间折半，迭代次数无疑是按照对数单调递减的。

解法框架

现在来看看二分查找的基本解法框架，参考C语言的函数示例

int binSearch(int a[], int n, int v)
{
    int low, mid, high;
    low = 0;
    high = ...;
    
    while (...) {
        mid = low + (high - low) / 2;
        if (a[mid] < v) {
            low = ...;
        } else if (a[mid] > v) {
            high = ...; 
        } else { /* a[mid] == v */
            ...;
        }
    return ...;
}

对应于契约编程的原理，我们可以如下说明各项要素：

  • 先决条件：函数输入已经预先排好的升序整数数组a[]，数组一共有n个元素，要查找的数值为v。
  • 后置条件：如果v存在于数组a[]中，输出其索引值；否则返回-1。
  • 循环不变式：如果v存在于数组a[]中，则其一定在每次循环的当前区间内，即位于上下界low和high之间。
  • 限定函数：因为下界low和上界high会根据v与当前的中间元素a[mid] 比较的结果而改变，总体区间是不断缩减的，while循环被限定。

无疑这些给我们理清了二分查找编程实现的思路，但是其中5个标记 ... 的部分，就是可能出现细节问题的地⽅。它们直接影响循环不变式的成立和限定函数的功用，细微的不同就会产生错误的结果，从而破坏后置条件。严重时还会造成无限循环或程序崩溃。

在具体的函数实现中，循环不变式是用特定的变量和数值来正式确定的。依据不同的“当前区间”的表示方法，二分查找有两大类实现方式：对称边界解法和不对称边界解法。

对称边界解法

对称边界解法是二分查找函数的最直观实现。对称边界解法定义的“当前区间”是 \(a[low] <= a[i] <= a[high]\)，即如果要找的元素存在于数组中，那么它的索引值 \(i∈[low,high]\)，此循环不变式应该一直成立！

由此，low被初始化为0，high被初始化为n-1。下面是这个解法的C语言实现：

二分查找基本解法 - 对称边界、闭合区间 [low, high]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binSearch_sym(int a[], int n, int v)
{
    int low, mid, high;
    low = 0;
    high = n - 1;
    
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (a[mid] < v) {
            low = mid + 1;
        } else if (a[mid] > v) {
            high = mid - 1;
        } else { /* a[mid] == v */
            return mid;
        }
    return -1;
}

因为搜索区间是闭合的，当前区间的上下界可能相等，所以while语句内继续循环的条件应该是low <= high，而不是low < high，即二者相等时还要再搜索。

在循环体内，中间元素a[mid]小于目标值v时，下次搜索的区间下界一定在mid的右侧，所以low = mid + 1；反之当中间元素a[mid]大于目标值v时，下次搜索的区间上界一定在mid的左侧，所以high = mid - 1。这样保证了循环不变式持续为真。

最后，如果low大于high，区间为空，循环中止，函数返回-1。这满足了后置条件。同时，因为上下界一直在相互靠近，当前区间不断缩小，函数实现隐含了限定函数对循环的限制作用。

注意： 上面循环代码的中间元素数组索引值的计算式是 mid = low + (high - low) / 2，而非 mid = (low + high) / 2。这时为了避免整数溢出的问题。

不对称边界解法

不对称边界解法是更为常见、应用更广的二分查找算法实现。不对称边界解法中的循环不变式基于的“当前区间”是 \(a[low] <= a[i] < a[high]\)，即如果要找的元素存在于数组中，那么它的索引值 \(i∈[low,high)\)。

不对称边界解法使用左闭右开的半闭合（或称半开放）搜索区间，这样做有很多好处，它使许多操作变得非常简单易懂：

  • 将一个区间一分为二，可以简单地选择一个支点并在两个新区间引用该支点： [low, high) -> [low, pivot), [pivot, high)
  • 区间内元素的计数可由一个单一的减法完成：high - low
  • 空区间的上下界索引都是相同的：[x, x)

下面给出了这个解法的两种C语言实现。第一种对应于数组输入，第二种适用于指针输入：

二分查找基本解法 - 数组输入，不对称边界、半闭合区间 [low, high)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binSearch_asym(int a[], int n, int v)
{
    int low, mid, high;
    low = 0;
    high = n;
    
    while (low < high) {
        mid = low + (high - low) / 2;
        if (a[mid] < v) {
            low = mid + 1;
        } else if (a[mid] > v) {
            high = mid;
        } else { /* a[mid] == v */
            return mid;
        }
    return -1;
}
二分查找基本解法 - 指针输入，不对称边界、半闭合区间 [low, high)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binSearch_asym_ptr(int *a, int n, int v)
{
    int *low, *mid, *high;
    low = a;
    high = a + n;
    
    while (low < high) {
        mid = low + ((high - low) >> 1);
        if (*mid < v) {
            low = mid + 1;
        } else if (*mid > v) {
            high = mid;
        } else { /* *mid == v */
            return mid;
        }
    return NULL;

在数组输入的实现代码中，为了满足“当前区间”的条件，low被初始化为0，high被初始化为n。

因为搜索区间是半闭合的，当前区间的上下界不可能相等，所以while语句内继续循环的条件应该是low < high，而不是low <= high，即二者相等时就不必再搜索了。

在循环体内，中间元素a[mid]小于目标值v时，下次搜索的区间下界一定在mid的右侧，所以low = mid + 1；反之当中间元素a[mid]大于目标值v时，下次搜索的区间上界就是mid，所以high = mid，此时上界还是开放的，\(i∈[low,high)\) 依然成立。这同样保证了循环不变式持续为真。

最后，如果low不小于high，区间为空，循环中止，函数返回-1。这满足了后置条件。同理，因为上下界一直在相互靠近，当前区间不断缩小，函数实现隐含了限定函数对循环的限制作用。

因为指针寻址比数组下标索引运算要快，许多二分查找函数使用指针输入。在这种情况下，下界low被赋值为第一个元素的指针a，上界high则为a + n。循环体内中间元素的指针的计算要小心，下面的两种写法都是错误的：

  1. mid = (low + high) / 2 - 这里问题不是运行时整数溢出，而是根本无法编译，因为将两个指针相加没有意义。
  2. mid = low + (high - low) >> 1 - C语言的移位运算符的优先级低于算术运算符，所以这一行等效于将high右移一位，显然是错误的。

正确的实现应该是 mid = low + ((high - low) >> 1)。

另外，在指针输入的情况下，后置条件是不一样的。二分查找函数要返回空指针以表明找不到目标值。

变形问题

掌握了契约编程的思想和循环不变式的原则，不仅可以编写出正确的基本算法实现，还能够解决一些变形的二分查找问题。

边界搜索

当有序数组中存在多个重复元素与目标值相同时，常常需要找到第一个（最左边）或最后一个（最右边）的元素的位置，这正是不对称边界解法展示威力的时候。

应用相同的循环不变式 \(a[low] <= a[i] < a[high]\)，也可以找到目标值的左右边界。不一样的地方是，如果中间值相同时，还要继续循环，以便定位第一个或最后一个元素。

定位左边界

要定位左边界时，如果中间元素小于目标值，则要找的元素的左边界一定在中间元素的右侧，需要将下界加一（右移一位）。如果中间元素大于目标值，要将上界设为中间元素的位置，继续搜索。而当中间元素与目标值相等时，因为其左边可能还有相同的元素，也要将上界设为中间元素的位置。在这些操作后，因为最后要找的元素索引值总是满足 \(i∈[low,high)\) 的条件，循环不变式恒为真。

而在循环结束时，为符合后置条件。需要对下界做一些检查。如果下界值为n，此数组索引值已越界，说明目标值比所有元素都大，函数应该返回-1。如果下界对应的元素正好目标值一样，输出下界索引值；否则返回-1。

以有序数组 [2, 5, 5, 5, 7, 7, 7, 8, 10] 为例，查找目标值5时的算法的执行过程如下表所示

循环次数 0 1 2 3 4 5 6 7 8
0（初始化） 2 (low) 5 5 5 7 (mid) 7 7 8 10 (high)
1 2 (low) 5 5 (mid) 5 7 (high) 7 7 8 10
2 2 (low) 5 (mid) 5 (high) 5 7 7 7 8 10
3 2 (low/mid) 5 (high) 5 5 7 7 7 8 10
4（结束） 2 5 (low/high) 5 5 7 7 7 8 10

可以看到，三轮循环过后上下界的索引值相等，都为1。对应的数组元素与目标值一样，所以输出为1。结果正确。以下是C语言实现的能定位左边界的二分查找函数

二分查找 - 定位左边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binSearch_leftbound(int a[], int n, int v)
{
    int low, mid, high;
    low = 0;
    high = n;
    
    while (low < high) {
        mid = low + (high - low) / 2;
        if (a[mid] < v) {
            low = mid + 1;
        } else { /* a[mid] >= v */
            high = mid;
        }
    }
    if (low == n) return -1; /* v is greater than all */
    return a[low] == v ? low /* find the left bound */
                       : -1; /* v is less than all */
}

定位左边界的解法还可以用于定位最后一个小于目标值的元素。比如，给定目标值为7，从左到右最后一个小于目标值的元素是第三个5（索引值为3），即目标值7的左边界的左邻居。而给定目标值为5时，从左到右最后一个小于目标值的元素是2，即搜索目标值5时循环结束后下界索引值减一。由此可见，这里循环不变式完全一样，只是后置条件有所不同：

  • 如果目标值不大于数组序列首个元素，返回-1。
  • 否则返回搜索结果的下界索引值减一。

对应的C语言实现如下

二分查找 - 定位最后一个小于目标值的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binSearch_lastlesser(int a[], int n, int v)
{
    int low, mid, high;
    low = 0;
    high = n;

    while (low < high) {
        mid = low + (high - low) / 2;
        if (a[mid] < v) {
            low = mid + 1;
        } else { /* a[mid] >= v */
            high = mid;
        }
    }
    return low == 0 ? -1        /* v is not greater than all */
                    : low - 1;  /* find the last lesser */

定位右边界

要定位右边界时，如果中间元素大于目标值，则要找的元素的右边界一定在中间元素的左侧，需要将上界设为中间元素的位置。如果中间元素小于目标值，要将下界加一（右移一位），继续搜索。而当中间元素与目标值相等时，因为其右边可能还有相同的元素，也要将下界设为中间元素的位置。在这些操作后，因为最后要找的元素索引值总是满足 \(i∈[low,high)\) 的条件，循环不变式恒为真。

同样在循环结束时，为符合后置条件。需要对下界做一些检查。如果下界值为0，说明目标值比所有元素都小，函数应该返回-1。如果下界的左边对应的元素正好目标值一样，输出下界左移一位的索引值；否则返回-1。

以相同的有序数组 [2, 5, 5, 5, 7, 7, 7, 8, 10] 为例，查找目标值7时的算法的执行过程如下表所示

循环次数 0 1 2 3 4 5 6 7 8
0（初始化） 2 (low) 5 5 5 7 (mid) 7 7 8 10 (high)
1 2 5 5 5 7 7 (low) 7 (mid) 8 10 (high)
2 2 5 5 5 7 7 7 (low) 8 (mid) 10 (high)
3 2 5 5 5 7 7 7 (low/mid) 8 (high) 10
4（结束） 2 5 5 5 7 7 7 8 (low/high) 10

可以看到，三轮循环过后上下界的索引值相等，都为7。对应左边的数组元素与目标值一样，所以输出为6。结果正确。以下是C语言实现的能定位右边界的二分查找函数

二分查找 - 定位右边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binSearch_rightbound(int a[], int n, int v)
{
    int low, mid, high;
    low = 0;
    high = n;
    
    while (low < high) {
        mid = low + (high - low) / 2;
        if (a[mid] > v) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    if (high == 0) return -1;          /* v is lesser than all */
    return a[high-1] == v ? (high - 1) /* find the right bound */
                          : -1;        /* v is greater than all */
}

同理，定位右边界的解法还可以用于定位第一个大于目标值的元素。比如，给定目标值为7，从左到右第一个大于目标值的元素是8（索引值为7），即目标值7的右边界的右邻居。而给定目标值为6时，从左到右第一个大于目标值的元素是第一个7，即搜索目标值6时循环结束后上界索引值。同样，这里循环不变式完全一样，只是后置条件有所不同：

  • 如果目标值不小于数组序列末尾元素，返回-1。
  • 否则返回搜索结果的上界索引值。

对应的C语言实现如下

二分查找 - 定位第一个大于目标值的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binSearch_firstgreater(int a[], int n, int v)
{
    int low, mid, high;
    low = 0;
    high = n;

    while (low < high) {
        mid = low + (high - low) / 2;
        if (a[mid] > v) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return high == n ? -1    /* v is not lesser than all */
                     : high; /* find the first greater */
}

旋转数组

如果输入的数组并非是完全升序的，二分查找算法还能达到特定的搜索目的吗？这要取决于数组的序列特征。

考虑数组 [0,1,2,4,5,6,7]，旋转4次后变成 [4,5,6,7,0,1,2]，即后4位元素依次循环移位到前面。如果给定一个没有重复元素的旋转数组，我们可不可以使用二分查找算法找到其最小元素的位置（从而也推断出它的旋转次数）？答案是肯定的。

仔细观察旋转数组，我们可以发现一个普遍规律：当旋转次数不为零时，如果中间值大于左边（下界）的值，那么最小值就出现在中间值的右侧（例如，对于[4,5,6,7,0,1,2]，中间值是7，最小值0出现在7的右侧）；如果中间值小于左边（下界）的值，最小值一定不会出现在中间值的右侧。据此，初始化low为0，high为n-1，我们可以将循环不变式表述为：最小值的索引\(i\)总是包含在由low和high界定的子数组中，即 \(i∈[low,high]\)。

相应的Python函数实现如下

二分查找 - 寻找旋转数组的最小元素
1
2
3
4
5
6
7
8
9
10
11
def findMin(nums: list[int]) -> int:
    low, high = 0, len(nums) - 1
    while low < high:
        if nums[low] < nums[high]: # no rotation
            return nums[low]
        mid = (high + low) // 2
        if nums[mid] >= nums[low]:
            low= mid + 1
        else: # nums[mid] < nums[low]
            high = mid
    return nums[low]

程序说明：

  • 当nums[low] < nums[high]时，当前区间内数组无旋转（比如 [0,1,2,3,4,5,6,7] 或 [0,1,2]），从循环不变式的条件可以马上推断，nums[low]就是最小值。返回值满足后置条件。
  • 对于第二个if语句，当nums[mid]>= nums[low]时，通过总结的规律，我们知道最小值出现在中间值的右手边。这时候因为先决条件是数组没有重复元素，而nums[mid]>= nums[low]（等号只有在low与mid相同时才成立，这在区间只有两个元素是会发生），同时第一个if语句又确定了nums[high]比nums[low]小，所以中间值不可能是最小值。因此，我们可以将下界low设置为mid+1，循环不变式保持不变。
  • 对于nums[mid] < nums[low]的情况，我们知道，最小值出现在中间值的左手边。然而，中间值可以是最小值，因此我们将上界high设置为中间值以保持循环不变式为真。
  • 当low与 high相等时，上下界指向同一元素。这时退出循环，函数可返回nums[low]。

实际上，这就是刷题网站力扣（LeetCode）上第153号问题（寻找旋转排序数组中的最小值）的答案。

其实换一种思路，还可以得到此题的第二种解法。如果将中间值与最右侧（上界）进行比较，当中间值大于最右侧值时，最小值一定出现在中间值的右侧；当中间值小于最右侧值时，最小值一定不会出现在中间值的右侧。这一结论对于旋转次数为零及区间只剩两个元素时都成立！从这里我们可以修改Python实现如下

二分查找 - 寻找旋转数组的最小元素（解法2）
1
2
3
4
5
6
7
8
9
def findMin2(nums: list[int]) -> int:
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (high + low) // 2
        if nums[mid] > nums[high]:
            low= mid + 1
        else:
            high = mid
    return nums[low]

此解法的代码看起来更简洁一些，提交LeetCode后同样通过无误。

K邻近元素

下一个应用二分查找实现高效解法的例子，是力扣上第658号问题：找到 K 个最接近的元素。题目的要求描述如下

给定一个排序好的数组 arr，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

  • |a - x| < |b - x| 或者
  • |a - x| == |b - x| 且 a < b

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：

输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]

提示：

  • 1 <= k <= arr.length
  • 1 <= arr.length <= \(10^4\)
  • arr 按升序排列
  • \(-10^4\) <= arr[i], x <= \(10^4\)

此题的难度为中等，解法比较多。比较直观的一种解法是计算每个数组元素和 x 的差值的绝对值（即距离），然后最小堆实现找出距离最近的 k 个元素。无疑，这种解法时间复杂度是 \(O(n)\)。它没有利用数组升序排列的性质，效率不高。

第二种解法是使用双指针的排除法。由于最后要保留 k 个元素，我们就需要删除 n - k 个元素。由于数组是升序排列的，这些被排除的元素一定都在两端，所以可以使用左右两边相互碰撞的方法。从最左端和最右端开始碰撞对比， 谁与目标 x 的距离小，谁就保留，另一个数则删除。经过 n - k 次重复之后就找到了左边界，输出 arr[low, low+k]。这种解法时间复杂度依然是 \(O(n)\)。

还有更好的解法吗？其实应用二分查找，确实可以得到时间复杂度是 \(O(\log n)\) 的最优解。以 n = 7 的数组序列 [3,10,19,57,68,71,72] 为例，仔细观察 k = 3 时不同 x 值情况下的输出：

  • x = 5 => [3,10,19]
  • x = 20 => [10,19,57]
  • x = 45 => [19,57,68]
  • x = 64 => [57,68,71]
  • x = 72 => [68,71,72]

可以看到，不论输入值 x 的变化如何，输出结果一定是输入数组序列的子数组，其长度为 k。这相当于应用一个滑动窗口从输入数组中截取一个长度为 k 的子集。此子集的起始位置索引值一定在 [0, n - k] 范围内。所以定位符合要求的子数组，等同于查找一个最优的起始位置 \(i∈[0,n-k]\)。因为数组是升序排列的，只要每次循环中保证最优的起始位置一定在收缩的区间内，二分查找就是可行的。

然而，在循环体内如何判定舍弃哪一半呢？这似乎是一个难题。对此，我们可以考察 [mid, mid + k] 区间，比较两端（即arr[mid] 与 arr[mid + k]）和 x 的距离，来决定最优解的窗口应该朝哪个方向滑动。以同样数组序列 [3,10,19,57,68,71,72] 和输入 k and x 数值为例，下表总结了五种可能的情况：

x arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] 判定 更新
5 3(low) 10 19(mid) 57 68(high) 71 72 x 位于区间左侧边界外 舍弃右半区间 (high = mid)
20 3(low) 10 19(mid) 57 68(high) 71 72 x 在区间内，靠近左侧边界 舍弃右半区间 (high = mid)
45 3(low) 10 19(mid) 57 68(high) 71 72 x 在区间内中心位置 舍弃右半区间 (high = mid)
64 3(low) 10 19(mid) 57 68(high) 71 72 x 在区间内，靠近右侧边界 舍弃左半区间 (low = mid + 1)
72 3(low) 10 19(mid) 57 68(high) 71 72 x 位于区间右侧边界外 舍弃左半区间 (low = mid + 1)

说明：

  • 对于此输入数组序列，n = 7, k = 3，所以初始化二分查找的上下界分别为 0 和 4，中间位置索引值 mid = 2。考察的区间为 [2, 5]，对应子数组 [19,57,68,71]。这些元素在上表中都用下划线标出。
  • 当输入 x 数值为5时，x 位于考察区间对应的子数组左侧边界外。无疑最优解的起始位置不可能在元素 19 右侧，因为那边的元素的数值离 x 越来越远。我们可以放心地舍弃右半区，更新 high = mid。
  • 当输入 x 数值为20时，(20 - 19) < (71 - 20)，所以 x 在区间内且靠近左侧边界。此时最优解的起始位置也不可能在元素 19 右侧。同样我们舍弃右半区，更新 high = mid。
  • 当输入x 数值为45时，(45 - 19) = (71 - 45)，所以 x 正好在考察区间中点。依据题目的要求，左右距离相等时选择左侧的点。我们一样舍弃右半区，更新 high = mid。
  • 当输入 x 数值为64或72时，x 要么位于区间内靠近右侧边界，要么位于区间右侧边界外。此时最优解的起始位置不可能在元素 57 左侧。我们可以舍弃左半区，更新 low = mid + 1

确定了循环更新的判定后，就可以直接编写Python代码实现了。对于上面的五种情况，虽然每一种都可以写出单独的比较语句，但这样程序效率太低了。实际上，舍弃左半区的两种情况用一个判定语句 (x - arr[mid]) > (arr[mid + k] - x) 就可以了。x 位于区间内靠近右侧边界时，这一条件判定当然为真。而当 x 位于区间右侧边界外时，此式的右边为负、左边为正，判定还是为真。对于其他三种舍弃右半区的情况，此判定都为假。由此我们得到Python函数实现如下：

1
2
3
4
5
6
7
8
9
def findClosestElements(arr: list[int], k: int, x: int) -> list[int]:
    low, high = 0, len(arr) - k
    while low < high:
        mid = (low + high) // 2
        if (x - arr[mid]) > (arr[mid + k] - x):
            low = mid + 1
        else:
            high = mid
    return arr[low:(low + k)]

此代码中 while 循环继续的条件是 low < high，似乎与对称边界（\(i∈[0,n-k]\)）的一般解法不符。其实这是因为当low和high相等时，我们已经得到了最优解，不必再进入循环体。

N次方根

另一类可用二分查找算法解决的变形问题，就是求方根。在前文“平方根运算”，就分别讲解了计算整数和浮点数平方根的二分查找/搜索算法实现。这里再给出一个通用的计算整数 n 次方根的二分查找算法。

对于整数 n 次方根，契约编程的各项要素是不同于数组输入的二分查找算法的。以下逐一加以说明：

  • 先决条件：函数输入是两个整数 v 和 n，目标是求 v 的 n 次方根的整数部分。
  • 后置条件：输出为一个不小于零的整数，为 v 的 n 次方根取整后的值。
  • 循环不变式：这里的搜索空间是从1到 n 的整个自然数集合。每次循环中，v 的整数 n 次方根都会在当前左闭右开区间内 [low, high)
    • 下界 \(low\leqslant \lfloor\sqrt[n]{x}\rfloor\)
    • 上界 \(high >\lfloor\sqrt[n]{x}\rfloor\)
  • 限定函数：因为上下界会根据 v 与当前的中间元素比较的结果而改变，总体区间不断缩减的，循环次数被限定。

显然，在循环体内确定上界或下界更新的断定条件，应该是中间值的 n 次幂和目标值 v 的比较结果。由此，得到求整数 n 次方根的不对称边界解法的Python语言实现如下：

二分查找 - 求整数n次方根
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binSearch_introot(v: int, n: int) -> int:
    """
    Use the binary search method to find out the integer
    component of the n'th root of v, an integer i such that
    i ** n <= v < (i + 1) ** n.
    """
    assert(v >= 0)
    
    low, mid, high = 0, 0, v
    while low < high:
        mid = (low + high) // 2
        power = mid ** n
        if power < v:
            low = mid + 1
        elif power > v:
            high = mid
        else: # power == v
            return mid
    return low - 1 if low > 1 else low

此外，在循环结束后，为满足后置条件，我们要检查low的数值。因为low的值在循环终止前被赋值mid + 1，而此操作使得low < high不再为真，所以必须减一。例外是输入 v 值为 1 的情况。

常见错误

下面是面试者在回答二分查找的编程实现问题时经常出现的错误：

  • 不能正确处理零元素或单个元素数组的情况（这时会出现上下界与中间位置重合）
  • 不能在数组的第一个或最后一个元素中找到目标值的情况，可能是初始化上下界造成的问题
  • 不能处理数组中的重复元素，特别是重复元素跨越两个子区间时
  • 不能处理目标值不存在造成的搜索失败的情况，原因也可能源自错误的上下界初始值
    • 对称边界解法使用闭合区间 \(i∈[low,high]\)，通常应该设定low = 0和high = n - 1
    • 不对称边界解法使用半闭合区间 \(i∈[low,high)\)，通常应该设定low = 0和high = n
  • 没有正确设定 while 循环继续的条件，不理解使用 <= 和 < 的区别
    • 对称边界解法一般使用low <= high (但也有例外，参见旋转数组和K邻近元素）
    • 不对称边界解法一般使用low < high，因为 low 应该总是小于 high。
  • 在探测后缩小区间时，没有正确设定子区间的端点，导致无限循环
    • 如果循环继续的条件是low <= high，则更新式一般为low = mid + 1或high = mid - 1
    • 如果循环继续的条件是low < high，则更新式一般为low = mid + 1或high = mid
  • 不能正确计算当前区间中间位置的索引值、地址（指针）值或用作比较的元素值
    • 计算中间位置索引时整数溢出：(low + high) / 2 或(low + high) >> 1（C/C++/Java编程实现时会发生，Python用 (low + high) // 2 OK）
    • 计算中间位置地址时做错误地使用指针相加运算：(low + high) / 2（C/C++编程实现时会发生）
    • 计算中间位置元素值时结果溢出：mid * mid（C/C++/Java编程实现时会发生，Python OK）

如果深入理解契约编程，牢记二分查找的基本解题框架，写出正确的循环不变式并将其保持为真的思想贯彻在编程中，再特别留意以上几点容易出错的地方，就一定可以提交令人满意的答案。

Glibc 库函数

在实际的应用系统开发时，一般不需要自己去写二分查找程序，更普遍的是调用已有的库函数。最后，介绍一下流行的Glibc库提供的二分查找工具函数 — bsearch()：

Glibc bsearch
1
2
3
4
5
#include <stdlib.h>

void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

对它的简要说明如下

描述

bsearch()函数在由nmemb对象组成的数组中搜索一个与key指向的对象匹配的成员。数组的第一个成员的位置由base指定，每个成员的存储空间大小为size。

数组的内容应该根据比较函数compar以升序排序。 compar函数应该有两个参数，依次指向key对象和数组成员。如果发现key对象分别小于、等于或大于数组的成员，函数应该返回一个小于、等于或大于零的整数。

返回值

bsearch()函数返回一个指向数组中匹配成员的指针，如果没有找到匹配的成员，则返回NULL。如果有多个成员匹配key对象，返回的元素是不确定的。

可以看到，应用此函数时调用者必须传递一个与数组元素类型相关的比较函数compar()。如果面试时的问题给出了数组元素类型的结构定义，求职者应该能够写出正确的compar()实现和调用bsearch()的完整工作无误的程序。

作为参考，bsearch()函数的完整实现如下

glibc/bits/stdlib-bsearch.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
__extern_inline void *
bsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size,
	 __compar_fn_t __compar)
{
  size_t __l, __u, __idx;
  const void *__p;
  int __comparison;
  __l = 0;
  __u = __nmemb;
  while (__l < __u)
    {
      __idx = (__l + __u) / 2;
      __p = (const void *) (((const char *) __base) + (__idx * __size));
      __comparison = (*__compar) (__key, __p);
      if (__comparison < 0)
	__u = __idx;
      else if (__comparison > 0)
	__l = __idx + 1;
      else
	{
#if __GNUC_PREREQ(4, 6)
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wcast-qual"
#endif
	  return (void *) __p;
#if __GNUC_PREREQ(4, 6)
# pragma GCC diagnostic pop
#endif
	}
    }
  return NULL;
}

很明显，它使用了不对称边界解法。注意第12行，计算中间索引值的表达式(__l + __u) / 2似乎会产生整数溢出。实际上因为__nmemb不会大到超出段地址的范围，所以这不会发生。库函数的实现者这里以性能作为优先考虑。