掌握Java二分搜索（从零开始学会高效查找算法）

二分搜索的工作原理

假设我们有一个升序排列的整数数组，要查找目标值 target：

1. 设置两个指针：left = 0（起始位置）和 right = array.length - 1（结束位置）。
2. 计算中间位置：mid = left + (right - left) / 2（避免整数溢出）。
3. 比较 array[mid] 与 target：
• 如果相等，返回 mid（找到目标）。
• 如果 array[mid] < target，说明目标在右半部分，更新 left = mid + 1。
• 如果 array[mid] > target，说明目标在左半部分，更新 right = mid - 1。
4. 重复步骤2-3，直到 left > right，此时表示未找到目标，返回 -1。

Java实现二分搜索

下面是一个完整的Java二分搜索代码示例：

public class BinarySearch {    // 二分搜索方法    public static int binarySearch(int[] arr, int target) {        int left = 0;        int right = arr.length - 1;        while (left <= right) {            // 防止 (left + right) 溢出            int mid = left + (right - left) / 2;            if (arr[mid] == target) {                return mid; // 找到目标，返回索引            } else if (arr[mid] < target) {                left = mid + 1; // 在右半部分继续搜索            } else {                right = mid - 1; // 在左半部分继续搜索            }        }        return -1; // 未找到目标    }    // 测试方法    public static void main(String[] args) {        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};        int target = 7;        int result = binarySearch(sortedArray, target);        if (result != -1) {            System.out.println("目标 " + target + " 在索引 " + result + " 处找到。");        } else {            System.out.println("目标 " + target + " 未找到。");        }    }}

递归版本的二分搜索

除了循环实现，我们也可以用递归来写二分搜索：

public static int binarySearchRecursive(int[] arr, int target, int left, int right) {    if (left > right) {        return -1; // 基准情况：未找到    }    int mid = left + (right - left) / 2;    if (arr[mid] == target) {        return mid;    } else if (arr[mid] < target) {        return binarySearchRecursive(arr, target, mid + 1, right);    } else {        return binarySearchRecursive(arr, target, left, mid - 1);    }}// 调用方式// int result = binarySearchRecursive(sortedArray, target, 0, sortedArray.length - 1);

时间复杂度分析

二分搜索的时间复杂度为 O(log n)，其中 n 是数组长度。这意味着即使数组有百万个元素，最多也只需约 20 次比较就能找到目标！相比之下，线性搜索需要 O(n) 时间，在大数据量下效率极低。

使用场景与注意事项

• ✅ 适用于静态、已排序的数据集合。
• ❌ 不适用于未排序的数组（需先排序，但排序本身耗时 O(n log n)）。
• ✅ Java 标准库已提供 Arrays.binarySearch() 方法，可直接使用。
• ⚠️ 注意整数溢出问题：使用 mid = left + (right - left) / 2 而非 (left + right) / 2。

总结

通过本教程，你已经掌握了Java二分搜索的核心原理和两种实现方式。作为一项基础而强大的高效搜索算法，它在面试和实际开发中都极为常见。记住：只要数据有序，就优先考虑二分搜索！

现在，动手试试吧！修改上面的代码，尝试查找不同的目标值，观察输出结果。实践是掌握二分查找算法的最佳方式。

关键词回顾：Java二分搜索、二分查找算法、Java编程教程、高效搜索算法