Java 中 Binary Search 的空间复杂度分析

在 Java 中，二分查找（Binary Search）是一种高效的查找算法，适用于已排序的数据结构，如数组。二分查找的基本思想是通过不断缩小搜索范围来找到目标值。

空间复杂度分析

二分查找的空间复杂度主要取决于算法实现的方式。以下是两种常见的实现方式及其空间复杂度分析：

1. 迭代实现

迭代实现的二分查找通常使用几个变量来跟踪搜索范围的边界和中间位置。由于这些变量是固定数量的，不随输入规模的变化而变化，因此迭代实现的二分查找的空间复杂度是常数级别的，即 O(1)。

public int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

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

    return -1; // 表示未找到目标值
}

在这个实现中，left、right 和 mid 是三个变量，它们的数量不随输入数组的大小变化而变化，因此空间复杂度是 O(1)。

2. 递归实现

递归实现的二分查找会在每次递归调用时在调用栈上分配新的空间来保存当前的状态（如 left、right 和 mid 的值）。递归调用的深度取决于输入数组的大小，通常是 O(log n)，因为每次递归调用都会将搜索范围减半。

因此，递归实现的二分查找的空间复杂度是 O(log n)。

public int binarySearchRecursive(int[] array, int target, int left, int right) {
    if (left > right) {
        return -1; // 表示未找到目标值
    }

    int mid = left + (right - left) / 2;

    if (array[mid] == target) {
        return mid;
    } else if (array[mid] < target) {
        return binarySearchRecursive(array, target, mid + 1, right);
    } else {
        return binarySearchRecursive(array, target, left, mid - 1);
    }
}

在这个实现中，每次递归调用都会在调用栈上分配新的空间，递归调用的深度是 O(log n)，因此空间复杂度是 O(log n)。

总结

• 迭代实现的二分查找：空间复杂度为 O(1)。
• 递归实现的二分查找：空间复杂度为 O(log n)。

在实际应用中，如果对空间复杂度有严格要求，通常会选择迭代实现的二分查找。