Library: bsearch()

bsearch() module is a function, which does an efficient binary search for a value in a sorted array. It returns an index before which the searched value can be inserted without violations of sorting.

To say differently: a returned index will point to the first element, which is bigger or equal to the searched value, or right beyond the array if the searched value is bigger than all elements of the array.

Usage

In a module-enabled environment (like Babel) it can be accessed like that:

import bsearch from '@researchnow/reno/src/utils/bsearch';

In global-based environments (like a browser) it is frequently mapped to Reno.utils.bsearch.

bsearch(sortedArray, value, less)

The function takes the following arguments:

• sortedArray is an array, which was already sorted using a criteria less.
• value is a value, we are looking for.
• less is an optional function:
  • It should take two arguments to compare:
    • The first one is an element from sortedArray.
    • The second one is value.
  • It should return a boolean-like value:
    • truthy if the first argument is less (in some sense of the word) than the second one.
    • falsy otherwise.
  • If not specified, < will be used directly, which is more efficient.

Examples

Equivalency of the default value:

bsearch(sortedArray, value) ===
  bsearch(sortedArray, value, (a, b) => a < b)

The insertion rule:

// we got some array of numbers
const unsorted = getSomeUnsortedArray();

// copy it and sort it using '<'
const sorted = unsorted.slice(0).sort((a, b) => a - b);

// define criteria of being sorted
const isSorted = array =>
  array.every((value, index) => index === 0 || array[index - 1] <= value);

assert(isSorted(sorted));

// find a position for a value
const index = bsearch(sorted, value);
sorted.splice(index, 0, value);

assert(isSorted(sorted));

The reverse sorting:

// we got some array of numbers
const unsorted = getSomeUnsortedArray();

// copy it and sort it using '>'
const sorted = unsorted.slice(0).sort((a, b) => b - a);

// define criteria of being sorted
const isReversedSorted = array =>
  array.every((value, index) => index === 0 || array[index - 1] >= value);

assert(isReversedSorted(sorted));

// find a position for a value
const index = bsearch(sorted, value, (a, b) => a > b);
sorted.splice(index, 0, value);

assert(isReversedSorted(sorted));