二分查找算法详解：基础版、平衡版与最左/右侧匹配

二分查找算法详解：基础版、平衡版与最左/右侧匹配

二分查找算法是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

基础版二分查找

基础版二分查找算法的基本步骤如下：

1. 数组必须是有序的
2. 定义左右边界索引 l 和 r，以及中间索引 m = (l + r) / 2
3. 根据 arr[m] 与目标值 target 的大小关系，不断调整左右边界

具体实现步骤：

（1）如果 target < arr[m]，则目标值在中间索引左侧，因此减少右边界索引 r = m - 1

（2）如果 target > arr[m]，则目标值在中间索引右侧，因此增加左边界索引 l = m + 1

（3）如果 target = arr[m]，则找到目标值，返回对应的索引

（4）如果循环结束时 l > r 还未找到目标值，返回 -1

基础版代码实现：

public static int binarySearch(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int m = (l + r) >>> 1;
        if (target < arr[m]) {
            r = m - 1;
        } else if (arr[m] < target) {
            l = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}

基础版二分查找算法性能分析：

1. 最好情况：O(1)，第一次循环就找到目标值
2. 最坏情况：O(log(n))

平衡版二分查找

在基础版二分查找中，如果目标元素位于数组的左侧，可能只需要 L 次循环就能找到，而如果位于右侧，则可能需要 2L 次。平衡版二分查找旨在优化这种不平衡性，使得在数组左侧和右侧查找的效率保持一致。

平衡版二分查找的实现思路：

1. 使用左闭右开的区间，即左边界索引 l 可能是目标值，而右边界索引 r 不可能是目标值
2. 不在循环内直接返回结果，而是等到循环只剩下 l 时退出，在循环外部比较 arr[l] 与 target

代码实现：

public static int binarySearch2(int[] arr, int target) {
    int l = 0, r = arr.length;
    while (1 < r - l) {
        int m = (l + r) >>> 1;
        if (target < arr[m]) {
            r = m;
        } else {
            l = m;
        }
    }
    if (arr[l] == target) {
        return l;
    } else {
        return -1;
    }
}

平衡版二分查找的时间复杂度在最好和最坏情况下都是 O(log(n))，没有 O(1) 的最好情况，因为需要在循环结束后额外判断是否找到目标值。

最左/右侧匹配的二分查找

在某些场景下，我们不仅需要找到目标值，还需要找到其在数组中的最左或最右侧位置。下面介绍如何实现这些特定需求的二分查找算法。

最左侧匹配的二分查找

实现思路：

1. 定义一个候选者变量 candidate
2. 如果找到目标值，将 m 赋值给 candidate，记录候选者位置
3. 继续缩小查找范围，重复更新候选者位置

代码实现：

public static int binarySearchLeftMost(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    int candidate = -1;
    while (l <= r) {
        int m = (l + r) >>> 1;
        if (target < arr[m]) {
            r = m - 1;
        } else if (arr[m] < target) {
            l = m + 1;
        } else {
            candidate = m;
            r = m - 1;
        }
    }
    return candidate;
}

最左侧匹配的二分查找 - 返回特定值

在某些情况下，我们希望在未找到目标值时返回一个有意义的值，例如返回大于等于目标值的最左侧索引。

代码实现：

public static int binarySearchLeftMost2(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int m = (l + r) >>> 1;
        if (target <= arr[m]) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return l;
}

测试用例：

System.out.println(binarySearchLeftMost2(new int[]{1, 2, 5, 5, 5, 8, 8, 8, 10, 22}, 7));
// 结果返回 5，即返回大于目标值 '7' 的最左侧元素 '8' 的索引位置

System.out.println(binarySearchLeftMost2(new int[]{1, 2, 5, 5, 5, 8, 8, 8, 10, 22}, 5));
// 返回 2，即找到目标值 '5' 的最左侧索引位置

最右侧匹配的二分查找

代码实现：

public static int binarySearchRightMost(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    int candidate = -1;
    while (l <= r) {
        int m = (l + r) >>> 1;
        if (target < arr[m]) {
            r = m - 1;
        } else if (arr[m] < target) {
            l = m + 1;
        } else {
            candidate = m;
            l = m + 1;
        }
    }
    return candidate;
}

最右侧匹配的二分查找 - 返回特定位置

代码实现：

public static int binarySearchRightMost2(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int m = (l + r) >>> 1;
        if (target < arr[m]) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return l - 1;
}

测试用例：

System.out.println(binarySearchRightMost2(new int[]{1, 2, 5, 5, 5, 8, 10, 22}, 7));
// 结果返回 4，即返回小于目标值 '7' 的最右侧元素 '5' 的索引位置

System.out.println(binarySearchRightMost2(new int[]{1, 2, 5, 5, 5, 8, 8, 8, 10, 22}, 8));
// 返回 7，即找到目标值 '8' 的最右侧索引位置

应用场景

这些不同版本的二分查找算法在实际问题中有着广泛的应用。例如：

• LeetCode 704 题：基本的二分查找
• LeetCode 35 题：使用最左侧匹配的二分查找

名词解析：

• 前任：小于目标值的最右侧元素（rightMost）
• 后任：大于目标值的最左侧元素（leftMost）
• 最近邻居：比较前任和后任与目标值的距离，选择距离更近的元素

本文原文来自博客园