This library contains functions for binary search of sorted arrays.
npm install --save @gmjs/binary-searchAll functions return an index of the found element or -1 if the element is not found.
Function have the following name formats:
binarySearchIndex<comparison-type>binarySearchIndex<comparison-type>Abitrary
There are five built-in 'comparison types' that can be used when searching:
Exact- Searched value must be exactly equal to the element.Lte- Returns the index of the largest element that is less than or equal to the searched value.Lt- Returns the index of the largest element that is strictly less than the searched value.Gte- Returns the index of the smallest element that is greater than or equal to the searched value.Gt- Returns the index of the smallest element that is strictly greater than the searched value.
The above comparison types are part of the function name. For example, if we wanted to have an exact search on a simple number array, we would use the function binarySearchIndexExact.
Binary search on simple number arrays have the following name format:
binarySearchIndex<comparison-type>
Binary search on arbitrary arrays have the following name format:
binarySearchIndex<comparison-type>Arbitrary
You are required to provide a comparison function that will be used to compare the searched value with the elements of the array.
Value and element do not have to be of the same type.
Arrays still need to be sorted with regards to the comparison function. This means, for example, that if the comparison function returns 'less than' for comparison of the input value with an element at index i, it should also return 'less than' for comparison of the input value with any element at index j where j > i.
All functions accept the following parameters:
value- The value to search for.array- The array to search in. Must be sorted.
Additionally, *Arbitrary functions also accept the following parameter:
compare- The comparison function to use.
Compare function has two parameters:
value- The value to search for.item- The element of the array the value is currently being compared to.
Function returns a number:
0- ifvalueis equal toitem.- Any negative value if
valueis less thanitem. - Any positive value if
valueis greater thanitem.
binarySearchIndexExact- Returns the index of the value in the array. Value needs to be exactly equal to the element at the index.binarySearchIndexExactArbitrary- Returns the index of the value in the array. Value needs to be exactly equal to the element at the index, as determined by the comparison function.binarySearchIndexLte- Returns the index of the largest element that is less than or equal to the value.binarySearchIndexLteArbitrary- Returns the index of the largest element that is less than or equal to the value, as determined by the comparison function.binarySearchIndexLt- Returns the index of the largest element that is strictly less than the value.binarySearchIndexLtArbitrary- Returns the index of the largest element that is strictly less than the value, as determined by the comparison function.binarySearchIndexGte- Returns the index of the smallest element that is greater than or equal to the value.binarySearchIndexGteArbitrary- Returns the index of the smallest element that is greater than or equal to the value, as determined by the comparison function.binarySearchIndexGt- Returns the index of the smallest element that is strictly greater than the value.binarySearchIndexGtArbitrary- Returns the index of the smallest element that is strictly greater than the value, as determined by the comparison function.
In the examples below, when using the number array functions, we will assume that the following array is initialized:
const array = [0, 10, ..., 100];When using the *Arbitrary functions, we will assume that the following comparison array is initialized:
interface Item {
readonly value: number;
}
const array = [
{ value: 0 },
{ value: 10 },
...
{ value: 100 }
];Also, when using the *Arbitrary functions, we will assume that the following comparison function is specified:
const compare = (value: number, item: Item): number => value - item.value;Returns the index of the value in the array. Value needs to be exactly equal to the element at the index.
const i1 = binarySearchIndexExact(10, array); // 1
const i2 = binarySearchIndexExact(100, array); // 10
const i3 = binarySearchIndexExact(15, array); // -1
const i4 = binarySearchIndexExact(-10, array); // -1
const i5 = binarySearchIndexExact(110, array); // -1Returns the index of the value in the array. Value needs to be exactly equal to the element at the index, as determined by the comparison function.
const i1 = binarySearchIndexExactArbitrary(10, array, compare); // 1
const i2 = binarySearchIndexExactArbitrary(100, array, compare); // 10
const i3 = binarySearchIndexExactArbitrary(15, array, compare); // -1
const i4 = binarySearchIndexExactArbitrary(-10, array, compare); // -1
const i5 = binarySearchIndexExactArbitrary(110, array, compare); // -1Returns the index of the largest element that is less than or equal to the value.
const i1 = binarySearchIndexLte(10, array); // 1
const i2 = binarySearchIndexLte(100, array); // 10
const i3 = binarySearchIndexLte(15, array); // 1
const i4 = binarySearchIndexLte(-10, array); // -1
const i5 = binarySearchIndexLte(110, array); // 10Returns the index of the largest element that is less than or equal to the value, as determined by the comparison function.
const i1 = binarySearchIndexLteArbitrary(10, array, compare); // 1
const i2 = binarySearchIndexLteArbitrary(100, array, compare); // 10
const i3 = binarySearchIndexLteArbitrary(15, array, compare); // 1
const i4 = binarySearchIndexLteArbitrary(-10, array, compare); // -1
const i5 = binarySearchIndexLteArbitrary(110, array, compare); // 10Returns the index of the largest element that is strictly less than the value.
const i1 = binarySearchIndexLt(10, array); // 0
const i2 = binarySearchIndexLt(100, array); // 9
const i3 = binarySearchIndexLt(15, array); // 1
const i4 = binarySearchIndexLt(-10, array); // -1
const i5 = binarySearchIndexLt(110, array); // 10Returns the index of the largest element that is strictly less than the value, as determined by the comparison function.
const i1 = binarySearchIndexLtArbitrary(10, array, compare); // 0
const i2 = binarySearchIndexLtArbitrary(100, array, compare); // 9
const i3 = binarySearchIndexLtArbitrary(15, array, compare); // 1
const i4 = binarySearchIndexLtArbitrary(-10, array, compare); // -1
const i5 = binarySearchIndexLtArbitrary(110, array, compare); // 10Returns the index of the smallest element that is greater than or equal to the value.
const i1 = binarySearchIndexGte(10, array); // 1
const i2 = binarySearchIndexGte(100, array); // 10
const i3 = binarySearchIndexGte(15, array); // 2
const i4 = binarySearchIndexGte(-10, array); // 0
const i5 = binarySearchIndexGte(110, array); // -1Returns the index of the smallest element that is greater than or equal to the value, as determined by the comparison function.
const i1 = binarySearchIndexGteArbitrary(10, array, compare); // 1
const i2 = binarySearchIndexGteArbitrary(100, array, compare); // 10
const i3 = binarySearchIndexGteArbitrary(15, array, compare); // 2
const i4 = binarySearchIndexGteArbitrary(-10, array, compare); // 0
const i5 = binarySearchIndexGteArbitrary(110, array, compare); // -1Returns the index of the smallest element that is strictly greater than the value.
const i1 = binarySearchIndexGt(10, array); // 2
const i2 = binarySearchIndexGt(100, array); // -1
const i3 = binarySearchIndexGt(15, array); // 2
const i4 = binarySearchIndexGt(-10, array); // 0
const i5 = binarySearchIndexGt(110, array); // -1Returns the index of the smallest element that is strictly greater than the value, as determined by the comparison function.
const i1 = binarySearchIndexGtArbitrary(10, array, compare); // 2
const i2 = binarySearchIndexGtArbitrary(100, array, compare); // -1
const i3 = binarySearchIndexGtArbitrary(15, array, compare); // 2
const i4 = binarySearchIndexGtArbitrary(-10, array, compare); // 0
const i5 = binarySearchIndexGtArbitrary(110, array, compare); // -1