Java案例如何实现二分查找？

wen java案例 2026-06-11 12

本文目录导读：

Java案例如何实现二分查找？

目录导读
二分查找是什么？为什么它如此高效？
Java实现二分查找的三大核心前提
手写二分查找：递归与迭代双版本代码解析
易错点深度剖析：边界条件与死循环陷阱
实战案例：在有序数组中寻找目标值的首个/最后一个位置
常见问题问答（FAQ）
总结与性能对比：二分查找 vs 线性查找

Java案例如何实现二分查找？从原理到实战，一篇读懂高效搜索算法

目录导读

二分查找是什么？为什么它如此高效？
Java实现二分查找的三大核心前提
手写二分查找：递归与迭代双版本代码解析
易错点深度剖析：边界条件与死循环陷阱
实战案例：在有序数组中寻找目标值的首个/最后一个位置
常见问题问答（FAQ）
总结与性能对比：二分查找 vs 线性查找

二分查找是什么？为什么它如此高效？

问答环节
Q：二分查找适用于什么样的数据？
A：二分查找（Binary Search）只适用于已排序的数据集合，它通过每次将搜索范围缩小一半的方式，快速锁定目标元素，在最坏情况下，时间复杂度仅为 O(log n)，而线性查找为 O(n)，在100万条数据中找目标值，线性查找最多需要100万次,而二分查找最多只需20次。

核心思想：

每次比较中间元素与目标值。
若中间值等于目标，结束。
若中间值大于目标，则搜索左半部分。
若中间值小于目标,则搜索右半部分。

Java实现二分查找的三大核心前提

没有这三个前提,二分查找会失效：

前提	说明
有序性	数组必须升序或降序排列，否则结果错误。
随机访问	必须能通过索引快速获取元素（数组或ArrayList），链表不适合，因为无法O(1)取中间元素。
单调性	目标值在数组中的位置遵循一致的比较逻辑（例如数字大小、字符串字典序）。

注意：Java中若使用 int[] 默认升序；若需降序,则需自定义比较逻辑。

手写二分查找：递归与迭代双版本代码解析

1 迭代版本（推荐，更高效）

public class BinarySearch {
    /**
     * 在升序数组nums中查找目标值target
     * @param nums 已排序的整型数组
     * @param target 要查找的目标值
     * @return 目标值的索引，若不存在返回-1
     */
    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            // 防止溢出：mid = left + (right - left) / 2 比 (left+right)/2 更安全
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;  // 目标在左半区
            } else {
                left = mid + 1;   // 目标在右半区
            }
        }
        return -1; // 未找到
    }
    public static void main(String[] args) {
        int[] arr = {-3, 0, 1, 5, 9, 12, 17};
        int target = 9;
        int index = binarySearch(arr, target);
        System.out.println("目标值 " + target + " 的索引为: " + index); // 输出4
    }
}

代码要点：

循环终止条件 left <= right 必须包含等号，否则当区间只有一个元素时可能漏判。
mid 计算使用 left + (right - left) / 2，避免 left + right 可能溢出 int 范围。

2 递归版本（更直观，但消耗栈空间）

public class BinarySearchRecursive {
    public static int search(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return search(nums, target, left, mid - 1);
        } else {
            return search(nums, target, mid + 1, right);
        }
    }
    public static void main(String[] args) {
        int[] arr = {-1, 0, 3, 5, 9, 12};
        int target = 5;
        int index = search(arr, target, 0, arr.length - 1);
        System.out.println(index); // 输出3
    }
}

递归 vs 迭代：

递归代码简洁，但深度过大会导致栈溢出（如数据量超过10万）。
生产环境推荐迭代版本,更安全且无额外函数调用开销。

易错点深度剖析：边界条件与死循环陷阱

❌ 错误1：循环条件写成 `left < right`

while (left < right) { // 错误！
    ...
}

后果：当区间仅剩一个元素（left == right）时，循环退出，漏判该元素，应使用 <=。

❌ 错误2：不更新 `mid` 或更新错误

if (nums[mid] > target) {
    right = mid;  // 错误！应该用 mid - 1
}

后果：当 nums[mid] 大于目标时，mid本身已无需再检查，应排除，同样，当小于目标时，left = mid + 1。

❌ 错误3：整数溢出陷阱

使用 (left + right) / 2 在 left + right 超过 Integer.MAX_VALUE 时（如 left=1500000000, right=1500000000）会溢出为负数。
正确写法：left + (right - left) / 2 或 (left + right) >>> 1（无符号右移）。

❌ 错误4：数组未排序

输入 [5, 1, 3, 7] 查找 3，二分算法会失败,因为数组不是升序或降序。

实战案例：在有序数组中寻找目标值的首个/最后一个位置

很多面试题要求找到重复元素的首个或最后一个位置，LeetCode 34题。

核心思路：

找第一个位置：当 nums[mid] == target 时，不直接返回，而是将 right = mid - 1，继续向左搜索。
找最后一个位置：当 nums[mid] == target 时，将 left = mid + 1,继续向右搜索。

代码实现

public class FirstLastPosition {
    // 找第一个等于target的索引
    public static int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                right = mid - 1; // 继续往左找
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
    // 找最后一个等于target的索引（对称逻辑）
    public static int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                left = mid + 1; // 继续往右找
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4};
        System.out.println("首个2位置: " + findFirst(arr, 2)); // 输出1
        System.out.println("最后2位置: " + findLast(arr, 2));  // 输出3
    }
}

应用场景：有序成绩排名中查找特定分数的所有学生区间；日志系统中按时间戳查找事件范围。

常见问题问答（FAQ）

问	答
Q1：Java数组必须升序吗？降序怎么处理？	降序需改为 `if (nums[mid] < target) right = mid - 1`，反直觉，建议先升序排序。
Q2：二分查找能用于浮点数吗？	可以，但双精度比较时注意精度误差，通常使用 `Math.abs(nums[mid] - target) < 1e-6` 判断相等。
Q3：如果数组中有重复元素，普通二分返回哪个位置？	不确定，可能是任意一个，如需固定位置，使用上面第5节的变种代码。
Q4：二分查找的递归版本会导致栈溢出吗？	当数组长度很大（如10万以上）时递归深度过大，会抛出 `StackOverflowError`，建议迭代。
Q5：Java JDK自带二分查找吗？	有！`Arrays.binarySearch(int[] a, int key)` 和 `Collections.binarySearch(List, key)`，但注意它们要求输入已排序。

总结与性能对比：二分查找 vs 线性查找

维度	二分查找	线性查找
时间复杂度	O(log n)	O(n)
空间复杂度	O(1)（迭代）	O(1)
数据要求	必须有序且支持随机访问	无要求
最适合场景	静态有序数据集，频繁搜索	小数据集或无序数据

最佳实践建议：

如果数据量小于100，线性查找更简单，因为二分查找的常数开销可能超过收益。
对于千万元素级别的数据库索引查询，二分查找及其变种（如B树）是核心基石。
在Java开发中，优先使用 Arrays.binarySearch 或 Collections.binarySearch,它们已高度优化且避免手写错误。

最后提醒：无论何时手写二分，务必用笔在纸上走一遍边界情况（空数组、单元素、目标在首尾），这种习惯能帮你避开90%的bug。

希望本文能帮助您在Java项目中准确、高效地实现二分查找，代码可复制直接运行，如有疑问欢迎在评论区交流探讨。