Conducts a binary search on a sorted array of items to find the index of a specific target.

binarySearch.ts

/**
 * Conducts a binary search on a sorted array of items to find the index of a
 * specific target. If the target is not found, it returns the nearest index
 * based on the comparator function.
 *
 * @param items - The sorted array of items to search within.
 * @param compare - A comparator function that returns:
 *   - a negative number if `item` is less than the target,
 *   - a positive number if `item` is greater than the target,
 *   - and 0 if `item` is equal to the target.
 *
 * @returns
 *   - The index of the target item if found.
 *   - `-1` if the comparator indicates the target is less than the first item.
 *   - `items.length` if the comparator indicates the target is greater than the
 *     last item.
 *
 * @template TItem - The type of items in the array.
 */
export function binarySearch<TItem = any>(
  items: TItem[],
  compare: (item: TItem, index: number) => number,
): number {
  let low = 0;
  let high = items.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const comparison = compare(items[mid], mid);

    if (comparison < 0) {
      low = mid + 1;
    } else if (comparison > 0) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  const finalCompare = compare(items[low], low);

  if (finalCompare < 0) {
    return low + 1;
  }
  if (finalCompare > 0) {
    return low - 1;
  }

  return low;
}