JS Standard Libraryv0.18.0

🔍 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,
  compare?: (a: T, b: T) => number
): number

Parameters

  • arr: The sorted array to search.

  • target: The value to find.

  • 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', (a, b) => a.length - b.length) //=> 1

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

// Objects by a key
const users = [{ id: 1 }, { id: 4 }, { id: 9 }];
binarySearch(users, { id: 4 }, (a, b) => a.id - b.id) //=> 1
Last updated on
Edit this page