ts-ds / search
Variable: search
const search: object;Defined in: search/index.ts:68
All search functions under short names: search.binary(array, target).
Type Declaration
binary
binary: <T>(array, target, compareFn?) => number = binarySearch;Finds the first element equal to target in a sorted array with binary search: compare with the middle element and continue in the half that can contain target.
| Time: best | Time: average | Time: worst | Memory |
|---|---|---|---|
| O(log n) | O(log n) | O(log n) | O(1) |
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.
exponential
exponential: <T>(array, target, compareFn?) => number = exponentialSearch;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.
interpolation
interpolation: (array, target) => number = interpolationSearch;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.
linear
linear: <T>(array, target, compareFn?) => number = linearSearch;Finds the first element equal to target by checking every element from the left.
Works on any array, sorted or not.
| Time: best | Time: average | Time: worst | Memory |
|---|---|---|---|
| O(1) | O(n) | O(n) | O(1) |
Type Parameters
| Type Parameter | Description |
|---|---|
T |
Parameters
| Parameter | Type | Default value | Description |
|---|---|---|---|
array | readonly T[] | undefined | Array to search. |
target | T | undefined | Value to find. |
compareFn? | CompareFn<T> | defaultCompare | Returns 0 for equal values. |
Returns
number
Index of the first equal element, or -1.
lowerBound
lowerBound: <T>(array, target, compareFn?) => number;Index of the first element that is not less than target in a sorted array — the position where target can be inserted keeping the order. Binary search: halves the range each step.
| Time | Memory |
|---|---|
| O(log n) | O(1) |
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 look for. |
compareFn? | CompareFn<T> | defaultCompare | Order of the array. |
Returns
number
From 0 to array.length.
upperBound
upperBound: <T>(array, target, compareFn?) => number;Index of the first element that is greater than target in a sorted array. upperBound − lowerBound is the number of elements equal to 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 look for. |
compareFn? | CompareFn<T> | defaultCompare | Order of the array. |
Returns
number
From 0 to array.length.