Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Binary Search (JS/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
}
@DominicTobias
Copy link
Author

DominicTobias commented Mar 21, 2022

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
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment