binary-search.js

/**
 * Binary search is a search algorithm that finds the position of a target value within a sorted array.
 * Binary search has O(log n) complexity.
 * @param {!Array} list The sorted array.
 * @param {*} item The item to search.
 * @return {number} Returns the index of the item in the array.
 * @see https://en.wikipedia.org/wiki/Binary_search_algorithm
 */
const binarySearch = (list, item) => {
  let low = 0;
  let high = list.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const guess = list[mid];

    if (guess === item) {
      // If the `item` is equal to the middle element, 
      // return the index of the middle element.
      return mid;
    }

    if (guess > item) {
      // If the `item` is less than the middle element, 
      // search in the left half.
      high = mid - 1;
    } else {
      // If the `item` is greater than the middle element, 
      // search in the right half.
      low = mid + 1;
    }
  }

  return null;
}