A seaswine. A mythical creature in Carta Marina

On Binary Search

I wanted to understand Binary Search, this is my attempt.

Suppose we have an array containing the elements [1, 2, 3, 4, 5, 6, 7]. In JavaScript we could use findIndex to locate the position of a specific element provided a value.

const nums = [1, 2, 3, 4, 5, 6, 7];
const indexOf4 = nums.findIndex((value) => value === 4);
// 3

However, if we would look up findIndex in the ECMAScript Specification we would find both merits and limits. The merit of findIndex would be that it’s a generic method that can handle different forms of data structures, given a data structure of type Object (that is, hashmaps and lists). On the other hand, the main limit is the runtime performance of the algorithm. findIndex is ‘linear’.

Let’s make a crude version of findIndex that is not generic and only deals with numbers for purposes of demonstration.

function onlyNumbersFindIndex(valueToFind, arrayToSearch) {
  const NOT_FOUND = -1;
  for(let index = 0; index < arrayToSearch.length; index++) {
    if( arrayToSearch[index] === valueToFind) {
      return index;
    }
  }
  return NOT_FOUND;
}

If the provided value is 5 and the list contains [1, 2, 3, 4, 5, 6], 5 would be found at position 4. This means that the algorithm, before finding 5, would examine 1, 2, 3, 4. Given a small dataset, we have no reason to implement an algorithm of our own, nothing would be gained and we would end up with unnecessary code. On the other hand, if the dataset is large much would be gained, depending on the size of the set.

In all fairness, I think the design choice for findIndex, a native method, is good. If we have a public API the linear way is the most reasonable.

And why? Other solutions would imply more och less the same preconditions as binary search: the list must be sorted ascendingly by value (and as a consequence sorted by comparable type). Binary Search is however not 'linear'.

Let’s have a look at binary search.

“In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.” — Wikipedia

Visual explanation

I think illustrations sometimes are better at explaining abstract notions and procedures. This is a visual explanation of binary search borrowed from Wikipedia. Although it does not demonstrate edgecases I think this picture summarizes the main abstraction very good.

Two JavaScript implementations

In a private repo, I recently did two solutions for this problem together with a friend, including test cases. This is a copy of my solutions.. To make it simple, they only deals with numbers.

Recursive version

const NOT_FOUND = -1;

function recursiveBS(numberToFind, array) {
  if(!isValueANumber(numberToFind)) {
    throw new Error('Value to find is not a number');
  } else if(
    array.length === 0 || numberToFind > array[array.length - 1] || numberToFind < array[0]
    ) {
      return NOT_FOUND;
  }
  function bs(
    low = 0,
    high = array.length,
        ) {
      const mid = Math.floor((low + high) / 2);
      if (
        array[mid] > numberToFind || (mid - 1 >= 0 && array[mid - 1] === numberToFind)
      ) {
        return bs(low, mid - 1);
      } else if (array[mid] < numberToFind) {
        return bs(mid + 1, high);
      } else if (array[mid] === numberToFind) {
        return mid;
      }
      return NOT_FOUND;
    }
  return bs();
}

function isValueANumber(value) {
  return typeof value === 'number' && !Number.isNaN(value); 
}

Imperative version

function imperativeBS(numberToFind, array) {
  if(!isValueANumber(numberToFind)) {
    throw new Error('Value to find is not a number');
  } else if(
    array.length === 0 || numberToFind > array[array.length - 1] || numberToFind < array[0]
  ) {
    return NOT_FOUND;
  }
  let low = 0;
  let high = array.length;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (array[mid] < numberToFind) {
      low = mid + 1;
    } else if (
      array[mid] > numberToFind || (mid - 1 >= 0 && array[mid - 1] === numberToFind)
    ) {
      high = mid - 1;
    } else if (array[mid] === numberToFind) {
      return mid;
    } else {
      return NOT_FOUND;
    }
  }       
}