binary-search.js

/**
* C++ fashion binary search in JavaScript
*/

/**
 * Core “first-true” search over a predicate.
 * Finds the smallest index i in [0…array.length) where predicate(array[i]) is true.
 * Returns array.length if none match.
 *
 * @param {Array<any>} array
 * @param {function(any): boolean} predicate
 * @returns {number}
 */
function binarySearchBase(array, predicate) {
  let low = 0;
  let high = array.length;

  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);

    if (predicate(array[mid])) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}

/**
 * First index where array[i] ≥ target
 *
 * @param {Array<any>} array
 * @param {any} target
 * @param {function(any, any): number} [compare=(a, b) => a - b]
 * @returns {number}
 */
function lowerBound(array, target, compare = (a, b) => a - b) {
  return binarySearchBase(array, element => compare(element, target) >= 0);
}

/**
 * First index where array[i] > target
 *
 * @param {Array<any>} array
 * @param {any} target
 * @param {function(any, any): number} [compare=(a, b) => a - b]
 * @returns {number}
 */
function upperBound(array, target, compare = (a, b) => a - b) {
  return binarySearchBase(array, element => compare(element, target) > 0);
}

/**
 * Exact-match binary search: returns index of `target` or -1 if not found.
 *
 * @param {Array<any>} array
 * @param {any} target
 * @param {function(any, any): number} [compare=(a, b) => a - b]
 * @returns {number}
 */
function binarySearch(array, target, compare = (a, b) => a - b) {
  const index = lowerBound(array, target, compare);

  if (index < array.length && compare(array[index], target) === 0) {
    return index;
  }

  return -1;
}

/**
 * Returns the half-open range [firstIndex, pastLastIndex) of all matches.
 *
 * @param {Array<any>} array
 * @param {any} target
 * @param {function(any, any): number} [compare=(a, b) => a - b]
 * @returns {[number, number]}
 */
function equalRange(array, target, compare = (a, b) => a - b) {
  return [
    lowerBound(array, target, compare),
    upperBound(array, target, compare),
  ];
}