@kmccullough/binary-search

binary-search

Performs a binary search by iterable or callback

Installation

$ npm install @kmccullough/binary-search

Usage

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

binarySearch( left: number, right: number, config: BinarySearchConfig ): BinarySearchIterator

Call binarySearch to create and configure a BinarySearchIterator for iteration.

BinarySearchConfig

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
}

BinarySearchIterator

[Symbol.iterator]()

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

splitRatio( ratio number ): BinarySearchIterator

ratio: number

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.

integer(): BinarySearchIterator

float(): BinarySearchIterator

By default, search is limited to integers. Call float to allow for deeper decimal search, but don't forget to end the search.

epsilon( value: number ): BinarySearchIterator

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.

startNext(): BinarySearchIterator

startLeft(): BinarySearchIterator

startRight(): BinarySearchIterator

startLow(): BinarySearchIterator

startHigh(): BinarySearchIterator

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.

done(): BinarySearchIterator

Call done during iteration to end iteration. 0 may also be returned from comparator search callback to end iteration.

left(): BinarySearchIterator

right(): BinarySearchIterator

lower(): BinarySearchIterator

higher(): BinarySearchIterator

Call left/right or lower/higher during iteration to direct next iterated value towards the desired bound.

nextValue( value: number ): BinarySearchIterator

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.

promote(): BinarySearchIterator

best: number | undefined

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.

clone(): BinarySearchIterator

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.

index: number

Current iteration index during iteration, or last iterated index after iteration.

value: number

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.

floatValue: number

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.

leftBound: number

rightBound: number

lowBound: number

highBound: number

Current iteration bounds.

isLeft: number

isRight: number

isLow: number

isHigh: number

True if current iteration value is equal to a bound.

positiveDirection: number

-1 if left bound is greater than right, otherwise 1

License

MIT