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

1.recursive binary search (with target position returned)

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 binary search (no target position returned, only boolean)

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);
}

I have a hard time understanding space complexity.

What are the space complexity of these two algorithms?

I think 2 has space complexity of O(log n) because on each function call of recursive binary search it to create a new list of size n/2, n/4... and so on (correct me if I am wrong). What about 1.recursive binary search (with target position returned)?



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source