ts-ds / exponentialSearch

Function: exponentialSearch()

function exponentialSearch<T>(
   array, 
   target, 
   compareFn?
): number;

Defined in: search/search.ts:103

Finds the first element equal to target in a sorted array: doubles an index (1, 2, 4, …) until it passes target, then runs binary search in the last range. Fast when target is near the beginning and for arrays of unknown length.

Time: best	Time: average	Time: worst	Memory
O(1)	O(log i)	O(log i)	O(1)

i is the position of target.

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	readonly T[]	undefined	Array sorted in the order of compareFn.
target	T	undefined	Value to find.
compareFn?	CompareFn<T>	defaultCompare	Order of the array.

Returns

number

Index of the first equal element, or -1.