recursiveBinarySearch.js

"use strict";

const expect = require("expect");

/**
 * Write a Binary Search Function using pure recursion
 */

const binarySearch = (sorted, value, index = 0) => {
  // Found the middle point in the sorted array
  let middle = Math.floor(sorted.length / 2);

  // If the value at the middle point is greater than value
  if (sorted[middle] > value) {
    //Recursively return the function, with a chunked array from the beginning to the middle and the remembered index
    return binarySearch(sorted.slice(0, middle), value, index);
  // If the value at the middle point is greater than value
  } else if (sorted[middle] < value) {
    // Recursively return the function, with a chunked array from the middle to the rest of the array
    // and the accumulative index value + the middle index value + 1
    return binarySearch(
      sorted.slice(middle + 1, sorted.length),
      value,
      index + middle + 1
    );
    // If not value found, return -1
  } else if (sorted[middle] !== value) {
    return -1;
    // Else, return the accumulative index value + the current middle point
  } else {
    return index + middle;
  }
};

// TDD
const handleFatalError = function(e) {
  console.log('Error:');
  console.log(e.message);
};

try {
  expect(binarySearch([1, 10, 15, 17, 20, 45], 10)).toBe(1);
  expect(binarySearch([1, 10, 15, 17, 20, 45], 45)).toBe(5);
  expect(binarySearch([1, 10, 15, 17, 20, 45], 987)).toBe(-1);
} catch (e) {
  handleFatalError(e);
  return;
}

console.log("All tests have passed!");