Performs a binary search by iterable or callback
$ npm install @kmccullough/binary-search
const LEFT = 0;
const RIGHT = 100;
const search = binarySearch(LEFT, RIGHT).startLow();
for (let [ value, index ] of search) {
search.isLeft ? search.right() : search.left();
}
console.log(search.value, search.index);
// Or if you prefer a callback...
const result = binarySearch(LEFT, RIGHT).startLow()
.search((value, index, control) => search.isLeft ? 1 : -1);
console.log(result);
// Log: 0, 100, 50, 25, 13, 6, 3, 2, 1
Call binarySearch
to create and configure a BinarySearchIterator
for iteration.
Configuration may be passed to the binarySearch
factory or configured through
various chained methods.
binarySearchConfig = {
startLeft: null, // True to start with leftmost value (default: startNext)
startRight: null, // True to start with rightmost value (default: startNext)
ratio: null, // Ratio used to choose next value (default: .5)
getNextValue: null, // Function callback to return next value
nextValue: null, // Next value to use when called for
epsilon: null, // Epsilon for float comparisons
float: null, // True to force no rounding of values
}
search( function( value: number, index: number, search: BinarySearchIterator ): number ): number | undefined
BinarySearchIterator
implements the Iterable
interface and can be used in a for loop.
Alternatively, the search
function is provided to instead provide a comparator
function which will return -1
, 1
, or 0
to direct the search left, right,
or to end the search.
getNextValue( function( left: number, right: number, index: number, search: BinarySearchIterator ): number ): BinarySearchIterator
By default, the next value is generated by applying the split ratio (default .5)
between left and right bounds. If a different ratio is desired, it may be changed
by calling the splitRatio
method.
For more complicated algorithms that decide which value to use next, passing
getNextValue
a callback function will replace the default implementation.
getNextValueByHalf
is also exported by the library in case you need the original.
The ratio
property is available to access the current ratio.
By default, search is limited to integers. Call float
to allow for deeper
decimal search, but don't forget to end the search.
For searches through decimal numbers with float
method, the default implementation
is to compare the current value against bounds within Number.EPSILON * 10
.
Call epsilon
to set a different value for epsilon for comparing floats.
By default, search starts at the next value (i.e. startNext
) between bounds,
and only then tests the bound towards the desired direction. Call startLeft
to start iteration at the left and right bounds, startRight
to start iteration at the right and left bounds, and startLow
/startHigh
to
start at the corresponding bounds based on order.
Call done
during iteration to end iteration. 0
may also be returned from
comparator search
callback to end iteration.
Call left
/right
or lower
/higher
during iteration to direct next iterated
value towards the desired bound.
Call nextValue
during or before iteration to set specific next iteration value.
Note that when setting the next value prior to iteration, this next value will
not be used until a next value is called for; for example, if startLeft
is also
called prior to iteration, then the left and right bounds would be tested first,
before this next value is used.
Call promote
during iteration to mark a value as the current "best".
Access best
property during or after iteration to access the last promoted value.
Passing true
for the best
argument of the search
method makes search
return this best value from the search
method, rather than the last value.
Clones the iterable for searching with the same configuration. Note that each call
to \[Symbol.iterator]
or search
will reset iteration, so running concurrent
searches with the same iterable is acceptable to do without cloning.
Current iteration index during iteration, or last iterated index after iteration.
Current iteration value during iteration, or last iterated value after iteration.
Note that this value is rounded to integer if not searching decimals with float
.
Current iteration value during iteration, or last iterated value after iteration.
Note that this value is the non-rounded value if searching decimals with float
.
Current iteration bounds.
True if current iteration value is equal to a bound.
-1 if left bound is greater than right, otherwise 1