ryangoree · September 14, 2023 22:04
diff --git a/binarySearch.ts b/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;
 }
	/**
	* 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;
	}