二分查找法

什么是二分查找

要解决的问题

在海量的数据中，如何以最快的速度定位到一个特定的目标？ 如果数据是无序的，我们只能像 “大海捞针” 一样逐个检查（线性查找）；但如果数据是有序的，我们就可以利用位置关系，成倍地缩小搜索范围。


核心思路

二分查找的核心是 “折半”。核心分成以下三个步骤：

  • 取中点：查看当前搜索区间的中间元素。
  • 做比较：
    • 如果目标等于中点，查找成功。
    • 如果目标小于中点，说明目标在左半部分，抛弃右半部分。
    • 如果目标大于中点，说明目标在右半部分，抛弃左半部分。
  • 循环：在新的区间内重复上述步骤，直到找到目标或区间为空。


优势和劣势

二分超找的优势：

  • 效率极高：时间复杂度为 $O(\log n)$。即使在 40 亿个数据中查找，最多也只需要 32 次比较。

  • 性能稳定：不像某些算法受数据分布影响波动较大。

二分查找的劣势：

  • 数据必须有序：这是硬性前提。如果数据频繁变动导致无法维持有序，维护成本会很高。
  • 物理存储要求：通常要求数据存储在支持随机访问（如数组）的结构中。


二分查找代码

二分查找交互演示
目标值:
RANGE [L, H]
[0, 11]
LOG
就绪

基本二分查找：这是最经典的形态，适用于数组中无重复元素，或只需找到任意一个目标的情况。

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
/**
 * 二分查找
 *
 * @param array  被查找的排好序的数组
 * @param target 查找目标
 * @return 目标在排好序数组中的位置
 */
private static int binarySearch(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        // 谨防直接写 (low+high)/2
        // 数组长度很大时相加的结果会超过 int 的最大值 2^31-1，导致变成负数（溢出）
        int mid = low + (high - low) / 2;

        if (target == array[mid]) {
            return mid;    // 命中返回索引
        } else if (target > array[mid]) {
            low = mid + 1; // 目标在右侧则收缩左边界
        } else {
            high = mid - 1; // 目标在左侧则收缩右边界
        }
    }
    return -1; // 没找到
}


查询第一个和最后一个：当数组中存在重复元素时，通过暂存结果并继续挤压区间的方法，可以精准定位边界。

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
33
34
35
36
37
38
39
40
41
42
43
/**
 * 寻找第一个出现的元素（左边界查找）
 */
private static int binarySearchFirst(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;
    int result = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (target == array[mid]) {
            result = mid;   // 找到了，先记下来
            high = mid - 1;  // 关键：继续往左边找，看还有没有更靠左的
        } else if (target > array[mid]) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

/**
 * 寻找最后一个出现的元素（右边界查找）
 */
private static int binarySearchLast(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;
    int result = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (target == array[mid]) {
            result = mid;  // 找到了，先记下来
            low = mid + 1; // 关键：继续往右边找，看还有没有更靠右的
        } else if (target > array[mid]) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}


插值查找法

对于大致均匀分布的数据 ，我们可以在二分查找的基础上做一个小优化。在二分查找中，我们的探测点 mid 永远是：$mid = low + \frac{1}{2} \times (high - low)$。而在插值查找中，mid 变成了自适应的：

$$mid = low + \frac{target - array[low]}{array[high] - array[low]} \times (high - low)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int binarySearch(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    // 注意：除了范围检查，target 必须在 array[low] 和 array[high] 之间，防止 mid 计算出界
    while (low <= high && target >= array[low] && target <= array[high]) {
        if (low == high) {
            if (array[low] == target) return low;
            break;
        }

        // 插值计算公式
        int mid = low + ((target - array[low]) * (high - low) / (array[high] - array[low]));

        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

效率的提升：对于 100 万个均匀分布的数据，二分查找需要约 20 次，而插值查找可能只需要 3-4 次。但需要说明的是，如果数据分布极不均匀（例如 [1, 2, 4, 8, 1000, 200000]），插值查找的预测会极其离谱，效率甚至不如线性查找。


实际的应用

二分查找在工业界不仅用于查找数字，还衍生出了许多变体：

  • 查找边界：在数据库索引查找中，用于定位 target 应该插入的位置，或查找第一个大于或小于某值的元素。
  • 数值分析：计算一个数的平方根（在 [0, x] 范围内二分）。
  • 分布式系统：一致性哈希（Consistent Hashing）中，在环状空间查找顺时针方向最近的服务节点。
  • 排错：著名的 git bisect 命令，利用二分查找在成百上千次提交（commit）中快速定位引入 bug 的那一次。


标题：
二分查找法
作者：
kinglyjn
声明：
引用 本文 请务必注明出处，原创不易，感谢尊重。