Java中的二分查找算法 | Baeldung中文网

1. 概述

本文将介绍二分查找相较于线性查找的核心优势，并展示其在Java中的具体实现方式。

2. 高效查找的必要性

假设我们经营一个葡萄酒电商平台，每天有数百万用户访问。用户通过应用筛选价格低于n美元的商品，从结果中选择并添加购物车。每秒都有海量查询需要快速响应。

后端算法最初使用线性查找，逐个比较用户价格限制与每瓶酒的价格，返回符合条件的商品。这种做法的时间复杂度为*O(n)*，意味着：

商品数量增长时，查询时间线性增加
新增商品会直接拖慢搜索速度

如果改用排序存储 + 二分查找，复杂度可优化至*O(log n)*：

数据量增长时，查询时间缓慢增加
性能提升非成比例，尤其适合大数据量场景

3. 二分查找

核心思路：将目标值(key)与数组中间元素比较，根据结果排除一半数据，在剩余部分继续查找。关键前提：数组必须已排序。若最终剩余部分为空，说明目标不存在。

3.1. 迭代实现

public int runBinarySearchIteratively(
  int[] sortedArray, int key, int low, int high) {
    int index = Integer.MAX_VALUE;
    
    while (low <= high) {
        int mid = low  + ((high - low) / 2);
        if (sortedArray[mid] < key) {
            low = mid + 1;
        } else if (sortedArray[mid] > key) {
            high = mid - 1;
        } else if (sortedArray[mid] == key) {
            index = mid;
            break;
        }
    }
    return index;
}

⚠️ 注意中间索引计算方式：int mid = low + ((high - low) / 2)
若直接使用 (low + high) / 2，当数组元素超过 2³⁰ 时可能溢出（sum 超过 int 最大值）。

3.2. 递归实现

public int runBinarySearchRecursively(
  int[] sortedArray, int key, int low, int high) {
    int middle = low  + ((high - low) / 2);
        
    if (high < low) {
        return -1;
    }

    if (key == sortedArray[middle]) {
        return middle;
    } else if (key < sortedArray[middle]) {
        return runBinarySearchRecursively(
          sortedArray, key, low, middle - 1);
    } else {
        return runBinarySearchRecursively(
          sortedArray, key, middle + 1, high);
    }
}

3.3. 使用 `Arrays.binarySearch()`

int index = Arrays.binarySearch(sortedArray, key);

直接调用 Java 工具类方法，传入已排序数组和目标值。

3.4. 使用 `Collections.binarySearch()`

int index = Collections.binarySearch(sortedList, key);

适用于 List 集合（需已排序），例如 ArrayList<Integer>。

3.5. 处理重复元素的排序数组

当数组含重复元素时，标准二分查找会返回任意匹配位置。若需获取所有匹配项（窗口范围），需修改逻辑：

查找首次出现位置

int startIndexSearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (sortedArray[mid] == target) {
            result = mid;
            right = mid - 1; // 继续向左搜索
        } else if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

查找末次出现位置

int endIndexSearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (sortedArray[mid] == target) {
            result = mid;
            left = mid + 1; // 继续向右搜索
        } else if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

获取所有匹配索引

List<Integer> runBinarySearchOnSortedArraysWithDuplicates(int[] sortedArray, Integer key) {
    int startIndex = startIndexSearch(sortedArray, key);
    int endIndex = endIndexSearch(sortedArray, key);
    return IntStream.rangeClosed(startIndex, endIndex)
      .boxed()
      .collect(Collectors.toList());
}

3.6. 性能分析

选择递归还是迭代实现主要看个人偏好，但需注意：

✅ 迭代优势：无栈开销，内存占用低，无栈溢出风险
❌ 递归劣势：
- 维护调用栈增加开销
- 大数据集可能触发 StackOverflowException
✅ 递归优势：代码更简洁易读

适用场景对比：

大数据量：二分查找显著优于线性查找
小数据量：线性查找可能更快（理论分析，需实测验证）

重要考量：二分查找要求数据已排序，排序本身有成本（如归并排序复杂度 *O(n log n)*）。需根据实际需求权衡。

4. 结论

本文介绍了二分查找算法的Java实现及适用场景。相比线性查找，它在处理大规模排序数据时能显著提升性能。实际应用中需结合数据规模、排序成本等因素综合选择。

完整代码示例见 GitHub仓库

Persistence

REST

Security