Binary Search (JS/TS)

binarySearch.ts

function binarySearch<T = any>(
  findValue: number,
  items: T[],
  getValue: (item: T) => number
) {
  let lo = 0
  let hi = items.length - 1

  while (lo <= hi) {
    const mi = (lo + hi) >>> 1
    const value = getValue(items[mi])

    if (findValue < value) {
      hi = mi - 1
    } else if (findValue > value) {
      lo = mi + 1
    } else {
      return mi
    }
  }

  return lo > 0 ? lo - 1 : 0
}

Reversed version:

function binarySearchDesc<T>(
  list: T[],
  target: number,
  getValue: (item: T) => number
): number {
  const lastIndex = list.length - 1
  let lo = lastIndex
  let hi = 0

  while (hi <= lo) {
    const mi = Math.floor(lo + hi)
    const value = getValue(list[mi])

    if (target < value) {
      hi = mi + 1
    } else if (target > value) {
      lo = mi - 1
    } else {
      return mi
    }
  }

  return hi > 0 ? hi - 1 : 0
}