这2个二分搜索算法的space复杂度一样吗？

Question

1.recursive二分查找（返回目标位置）

function recursiveBinarySearch(list, target) {
  const binarySearchHelper = (list, target, left, right) => {
    let mid = Math.floor((left + right) / 2);

    //not found
    if (left > right) {
      return -1;
    }

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

  return binarySearchHelper(list, target, 0, list.length - 1);
}

2.recursive二分查找（没有返回目标位置，只有布尔值）

function recursiveBinarySearch(list, target) {
  const binarySearchHelper = (list, target) => {
    let mid = Math.floor((list.length - 1) / 2);

    //not found
    if (list.length <= 0) {
      return false;
    }

    //found or recursive
    if (list[mid] === target) {
      return true;
    } else if (list[mid] < target) {
      return binarySearchHelper(list.slice(mid + 1), target);
    } else if (list[mid] > target) {
      return binarySearchHelper(list.slice(0, mid), target);
    }
  };

  return binarySearchHelper(list, target);
}

我很难理解 space 复杂性。

这两种算法的space复杂度是多少？

我认为 2 的 space 复杂度 为 O(log n) 因为在递归二进制搜索的每个函数调用中，它都会创建一个大小为 n/2、n/4... 的新列表（如果我错了请纠正我）。 1.recursive 二进制搜索（返回目标位置）怎么样？

Answer 1

不，space 复杂度不同（忽略初始数组的 O(n) 内存）

第一个算法的 space 复杂度为 O(log n)。您有 log n 个步骤，并且在每个步骤中您需要恒定数量的变量

第二种算法的 space 复杂度为 O(n)。创建大小为 n/2 的第一个副本已经 space 复杂度为 O(n)。您有 log n 个步骤。第 1 步需要 n/2 内存，第 2 步需要 n/4，第 3 步需要 n/8，... n/2 + n/4 + n/8 + 。 .. <= n 仍然是 O(n)。

这2个二分搜索算法的space复杂度一样吗？

Are the space complexity of these 2 Binary Search algorithm the same?

javascript

algorithm

recursion

binary-search

space-complexity