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)?

CodePudding user response：

No, the space complexity is not same (ignoring O(n) memory for the initial array)

The first algorithm has a space complexity of O(log n). You have log n steps and in each step you need a constant number of variables

The second algorithm has a space complexity of O(n). Creating the first copy with size n/2 has already space complexity O(n). You have log n steps. Step 1 requires n/2 memory, step 2 requires n/4, step 3 requires n/8, ... n/2 n/4 n/8 ... <= n is still O(n).