JS Standard Libraryv0.20.0

binarySearch

🔍 Finds the index of a value in a sorted array, in O(log n) comparisons.

Warning

The array must already be sorted by the same comparator. That is a precondition rather than something checked — verifying it would cost the O(n) scan this exists to avoid. An unsorted array gives a meaningless answer rather than an error.

Syntax

TypeScript
import { binarySearch } from '@opentf/std';
binarySearch<T>(
  arr?: T[],
  target: T,
  options?: { compare: (a: T, b: T) => number }
): number

Parameters

  • arr: The sorted array to search.

  • target: The value to find.

  • options.compare: Orders two values, as Array.prototype.sort does. Defaults to ordering by < and >.

Returns

The index of the first match, or -1 if there is none.

Behavior

  • indexOf scans every element, which is fine until the array is large and the lookup is in a loop. Where the array is already sorted, most of it never needs to be looked at.

  • The default comparator orders the way sort does, so an array from sort can be searched without one.

  • Where a value appears more than once the first of them is returned, so the answer does not depend on where the search happened to land.

Examples

TypeScript
binarySearch([1, 3, 5, 7, 9], 5) //=> 2

binarySearch([1, 3, 5, 7, 9], 1) //=> 0

binarySearch([1, 3, 5, 7, 9], 4) //=> -1

binarySearch(['ant', 'bee', 'cow'], 'cow') //=> 2

// The first of several equal values
binarySearch([1, 2, 2, 2, 3], 2) //=> 1
TypeScript
// A comparator decides what counts as a match, not just the order
binarySearch(['a', 'bb', 'ccc'], 'dd', { compare: (a, b) => a.length - b.length }) //=> 1

// Descending, searched with the comparator it was sorted by
binarySearch([7, 5, 3, 1], 5, { compare: (a, b) => b - a }) //=> 1

// Objects by a key
const users = [{ id: 1 }, { id: 4 }, { id: 9 }];
binarySearch(users, { id: 4 }, { compare: (a, b) => a.id - b.id }) //=> 1

Try it

Last updated on
Edit this page