ts-ds / interpolationSearch
Function: interpolationSearch()
ts
function interpolationSearch(array, target): number;Defined in: search/search.ts:128
Finds the first element equal to target in a sorted array of numbers by estimating its position from the values, like looking up a word in a dictionary: pos = low + (target − A[low]) · (high − low) / (A[high] − A[low]).
| Time: best | Time: average¹ | Time: worst | Memory |
|---|---|---|---|
| O(1) | O(log log n) | O(n) | O(1) |
¹ For uniformly distributed values. On skewed data (e.g. 1, 2, 3, …, 1 000 000) it degrades.
Parameters
| Parameter | Type | Description |
|---|---|---|
array | readonly number[] | Numbers sorted in ascending order. |
target | number | Number to find. |
Returns
number
Index of the first equal element, or -1.