Binary Search 在 Java 中的递归实现

在Java中，二分查找（Binary Search）是一种高效的查找算法，适用于已排序的数据集合。以下是二分查找的递归实现：

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40};
        int target = 10;
        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("元素不在数组中");
        } else {
            System.out.println("元素在数组中的索引为: " + result);
        }
    }

    public static int binarySearch(int[] arr, int target) {
        return binarySearchRecursive(arr, target, 0, arr.length - 1);
    }

    private static int binarySearchRecursive(int[] arr, int target, int low, int high) {
        if (low > high) {
            return -1; // 基本情况：目标值不在数组中
        }

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

        // 检查中间元素是否是目标值
        if (arr[mid] == target) {
            return mid;
        }

        // 如果目标值大于中间元素，则在右半部分继续查找
        if (arr[mid] < target) {
            return binarySearchRecursive(arr, target, mid + 1, high);
        }

        // 如果目标值小于中间元素，则在左半部分继续查找
        return binarySearchRecursive(arr, target, low, mid - 1);
    }
}

代码解释：

1. binarySearch 方法：这是对外的接口方法，调用递归方法 binarySearchRecursive 并传入初始的 low 和 high 索引。
2. binarySearchRecursive 方法：这是递归实现的核心方法。
   • 基本情况：如果 low 大于 high，说明目标值不在数组中，返回 -1。
   • 计算中间索引：使用 low + (high - low) / 2 来避免整数溢出。
   • 检查中间元素：如果中间元素等于目标值，返回中间索引。
   • 递归查找：如果目标值大于中间元素，则在右半部分继续查找；如果目标值小于中间元素，则在左半部分继续查找。

注意事项：

• 二分查找要求数组是有序的。
• 递归实现可能会导致栈溢出，特别是对于非常大的数组。在这种情况下，可以考虑使用迭代实现。

希望这个示例对你理解二分查找的递归实现有所帮助！