如何用Java实现递归Binary Search

在Java中，递归二分查找（Binary Search）是一种高效的查找算法，适用于已排序的数组。它通过每次将搜索范围缩小一半来快速定位目标元素。下面是递归二分查找的实现步骤以及示例代码。

实现步骤

1. 确定搜索范围：初始时，整个数组都是搜索范围。设定两个指针，low（最低索引）和high（最高索引）。

2. 计算中间索引：计算当前搜索范围的中间索引 mid = low + (high - low) / 2。这样可以避免直接相加可能导致的整数溢出。

3. 比较中间元素与目标值：

   • 如果 array[mid] == target，则找到目标，返回索引 mid。
   • 如果 array[mid] < target，目标在右半部分，递归调用左半部分。
   • 如果 array[mid] > target，目标在左半部分，递归调用右半部分。

4. 递归终止条件：

   • 当 low 超过 high 时，表示数组中不存在目标元素，返回 -1。

示例代码

public class BinarySearchRecursive {

    /**
     * 递归实现二分查找
     *
     * @param array  已排序的数组
     * @param target 目标值
     * @return 目标值的索引，如果未找到则返回-1
     */
    public static int binarySearch(int[] array, int target) {
        return binarySearchHelper(array, target, 0, array.length - 1);
    }

    /**
     * 辅助递归方法
     *
     * @param array  已排序的数组
     * @param target 目标值
     * @param low    当前搜索范围的最低索引
     * @param high   当前搜索范围的最高索引
     * @return 目标值的索引，如果未找到则返回-1
     */
    private static int binarySearchHelper(int[] array, int target, int low, int high) {
        if (low > high) {
            // 基本情况：目标不在数组中
            return -1;
        }

        // 防止 (low + high) 可能导致的溢出
        int mid = low + (high - low) / 2;

        if (array[mid] == target) {
            return mid; // 找到目标
        } else if (array[mid] < target) {
            return binarySearchHelper(array, target, mid + 1, high); // 在右半部分继续查找
        } else {
            return binarySearchHelper(array, target, low, mid - 1); // 在左半部分继续查找
        }
    }

    // 示例使用
    public static void main(String[] args) {
        int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
        int target = 14;

        int result = binarySearch(sortedArray, target);

        if (result != -1) {
            System.out.println("元素 " + target + " 在数组中的索引为: " + result);
        } else {
            System.out.println("元素 " + target + " 不在数组中。");
        }
    }
}

代码说明

1. binarySearch 方法：这是对外提供的接口方法，接受一个已排序的数组和目标值，调用辅助方法 binarySearchHelper 开始递归查找。

2. binarySearchHelper 方法：

   • 参数：
     • array: 已排序的数组。
     • target: 要查找的目标值。
     • low: 当前搜索范围的最低索引。
     • high: 当前搜索范围的最高索引。
   • 逻辑：
     • 首先检查 low 是否大于 high，如果是，说明目标不在数组中，返回 -1。
     • 计算中间索引 mid，避免直接相加可能导致的溢出。
     • 比较 array[mid] 与 target：
       • 相等则返回 mid。
       • 如果 array[mid] 小于 target，递归搜索右半部分（mid + 1 到 high）。
       • 如果 array[mid] 大于 target，递归搜索左半部分（low 到 mid - 1）。

3. main 方法：示例演示如何使用 binarySearch 方法。定义一个已排序的数组和一个目标值，调用 binarySearch 并输出结果。

注意事项

• 数组必须是有序的：二分查找适用于已排序的数组。如果数组未排序，必须先进行排序（例如使用 Arrays.sort()）再应用二分查找。

• 时间复杂度：二分查找的时间复杂度为 O(log n)，比线性查找的 O(n) 更高效，尤其适用于大规模数据。

• 递归深度：对于非常大的数组，递归调用可能导致栈溢出。在这种情况下，可以考虑使用迭代方式实现二分查找。

迭代实现（可选）

为了防止递归深度过大导致的栈溢出问题，可以使用迭代方式实现二分查找：

public static int binarySearchIterative(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

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

    return -1; // 未找到目标
}

你可以根据具体需求选择递归或迭代的方式来实现二分查找。