precise-bs

binary search and related utility functions

lowerIndex/lowerValue/lowerEntry

export function lowerIndex<Arr extends AnyArray>(
  array: Arr,
  find: Arr[number]
): number
export function lowerValue<Arr extends AnyArray, Find>(
  array: Arr,
  find: Find,
  comparator: Comparator<Arr[number] | Find>,
  low?: number,
  high?: number
): number

export function lowerValue<...>(...): Arr[number]
export function lowerEntry<...>(...): [number, Arr[number]]

Finds the index/value/entry of the least element less than the given search value in a sorted array using a binary search. If the search value is less than or equal to all elements in the array, returns the index -1 or value undefined or entry [-1, undefined].

floorIndex/floorValue/floorEntry

export function floorIndex<Arr extends AnyArray>(
  array: Arr,
  find: Arr[number]
): number
export function floorValue<Arr extends AnyArray, Find>(
  array: Arr,
  find: Find,
  comparator: Comparator<Arr[number] | Find>,
  low?: number,
  high?: number
): number

export function floorValue<...>(...): Arr[number]
export function floorEntry<...>(...): [number, Arr[number]]

Finds the index/value/entry of the least element less than or equal to the given search value in a sorted array using a binary search. If the search value is less than all elements in the array, returns the index -1 or value undefined or entry [-1, undefined].

ceilingIndex/ceilingValue/ceilingEntry

export function ceilingIndex<Arr extends AnyArray>(
  array: Arr,
  find: Arr[number]
): number
export function ceilingValue<Arr extends AnyArray, Find>(
  array: Arr,
  find: Find,
  comparator: Comparator<Arr[number] | Find>,
  low?: number,
  high?: number
): number

export function ceilingValue<...>(...): Arr[number]
export function ceilingEntry<...>(...): [number, Arr[number]]

Finds the index/value/entry of the least element greater than or equal to the given search value in a sorted array using a binary search. If the search value is greater than all elements in the array, returns the index array.length or value undefined or entry [array.length, undefined].

higherIndex/floorValue/floorEntry

export function higherIndex<Arr extends AnyArray>(
  array: Arr,
  find: Arr[number]
): number
export function higherValue<Arr extends AnyArray, Find>(
  array: Arr,
  find: Find,
  comparator: Comparator<Arr[number] | Find>,
  low?: number,
  high?: number
): number

export function higherValue<...>(...): Arr[number]
export function higherEntry<...>(...): [number, Arr[number]]

Finds the index/value/entry of the least element greater than the given search value in a sorted array using a binary search. If the search value is greater than or equal all elements in the array, returns the index array.length or value undefined or entry [array.length, undefined].

type Comparator<T>

The generic comparator type used by the above binary search functions.

export type Comparator<T> = (a: T, b: T) => number

DEFAULT_COMPARATOR

The default comparator used by the above binary search functions. This differs from the default Array.prototype.sort comparator, which stringifies values before comparing, and is one of the biggest pitfalls in JS!

export const DEFAULT_COMPARATOR: Comparator<any> = (a: any, b: any): number =>
  a < b ? -1 : a > b ? 1 : 0