二分查找的实现细节

最近留意到关于实现 二分查找算法(Binary Search Algorithm) 的一个小提醒,内容大致意思是:尽管算法思想很简单,但我们在正确实现二分查找的时候,仍需注意一下关于算法退出条件和中间值计算的相关细节。

本篇文章简单介绍二分查找算法,围绕相关的实现细节问题,做些浅显的分析。


简单介绍

在计算机科学中,二分查找也被称为折半查找、对数查找,是一种在有序数组中查找目标元素的搜索算法。

二分查找会将目标元素与数组中间元素进行比较,若不相等,则目标元素不存在的半段数组会被淘汰,并且查询会在目标元素存在的半段数组中继续进行,直到比较成功为止。如果查询以空数组为结束,则表示目标元素不存在。一次二分查找的具体过程可以参考下图(图片来源自维基百科):

iamge

二分查找的最差时间复杂度是 𝑶(log 𝒏),空间复杂度是 𝑶(1)。相比于最差时间复杂度为 𝑶(𝒏) 的 线性查找(Linear Search),二分查找执行更快、效率更高。相比于为快速查找量身定制的数据结构 哈希表(Hash Table),二分查找的限制更少、应用更广。

二分查找有许多不同的变种版本,例如 Fractional Cascading 加速了二分查找在多个数组中对相同数值的搜索速度,有效解决了计算机几何以及其它领域中的一系列搜索相关问题;Exponential Search 扩展了二分查找算法,使其可以应用于无界列表。

二分查找的算法思想也衍生出了许多其它数据结构和算法,例如 Binary Search TreeB-Tree


初步实现

以 Java 语言为例,初步实现一个简单的二分查找算法,演示代码如下:

public int binarySearch(int[] arr, int low, int high, int key) {
    // 算法退出条件
    if (low > high) {
        return -1;
    }

     // 计算本次查找的中间值
    int mid = (low + high) / 2;

     // 二分查找的判断逻辑
    if (arr[mid] < key) {
        return binarySearch(arr, mid + 1, high, key);
    } else if (arr[mid] > key) {
        return binarySearch(arr, low, mid - 1, key);
    } else {
        return mid;
    }
}

依据文章开头的小提醒 review 上例代码,可以发现其中存在着的细节问题:

  1. 缺少参数校验

    当输入参数 lowhigh 的数值小于零时,程序会存在逻辑错误。

  2. 递归查找的栈溢出

    当查找的次数足够多时,程序会抛出 java.lang.StackOverflowError 异常。

  3. 中值计算的整型溢出

    当查找的数组足够大时,直接使用 (low + high) / 2 计算二分查找过程中的中间数值,程序会存在整型数值溢出的问题。


正确实现

修复上述提及的三个问题,演示代码如下:

public int binarySearch(int[] arr, int low, int high, int key) {
    // 参数校验
    if (arr == null || arr.length == 0 || low < 0 || high < 0) {
        return -1;
    }

    while (true) {
        // 算法退出条件
        if (low > high) {
            return -1;
        }

        // 计算本次查找的中间值
        int mid = low + ((high - low) >>> 1);

        // 二分查找的判断逻辑
        if (arr[mid] < key) {
            low = mid + 1;
        } else if (arr[mid] > key) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
}