binarySearch

function · experimental

function binarySearch<T extends ArrayLike<number> | ArrayLike<bigint> | ArrayLike<string>>(haystack: T, needle: T[number]): number

Binary search within a sorted array, allowing for non-exact matches.

Binary searching may be preferable to Array#findIndex if the array is large and performance is at a premium, or if information about the insertion index is needed upon non-exact matches (Array#findIndex simply returns -1 in such cases).

haystack: T

The array to search. This MUST be sorted in ascending order, otherwise results may be incorrect.

needle: T[number]

The value to search for.

Returns

• If needle is matched exactly, the index of needle. If multiple elements in haystack are equal to needle, the index of the first match found (which may not be the first sequentially) is returned.
• Otherwise, the bitwise complement of needle's insertion index if it were added to haystack in sorted order.

import { binarySearch } from "@ende/collections/unstable-binary-search";
import { assertEquals } from "@ende/assert";

assertEquals(binarySearch([0, 1], 0), 0);
assertEquals(binarySearch([0, 1], 1), 1);
assertEquals(binarySearch([0, 1], -0.5), -1); // (bitwise complement of 0)
assertEquals(binarySearch([0, 1], 0.5), -2); // (bitwise complement of 1)
assertEquals(binarySearch([0, 1], 1.5), -3); // (bitwise complement of 2)