binarySearch.js

/**
 * Performs a recursive binary search upon the interval [min,max]
 * where `getDirection()` determines the direction of the current value
 * in relation to the reference value.
 *
 * Due to the properties of this algorithm,
 * reaching the solution will always take less than `⌈log₂(max-min)⌉` steps.
 *
 * @author Lara Sophie Schütt (@literallylara)
 * @license MIT
 *
 * @param {Number} opts.min 
 * The minimum, or left side of the interval
 * @param {Number} opts.max 
 * The maximum, or right side of the interval
 * @param {Number} [opts.bias=1]
 * The bias that defines the maximum allowed offset from the target value
 * @param {Boolean} [opts.round=false]
 * Whether or not to round the value including the argument to `getDirection()`
 * @param {Number} [opts.maxSteps=Infinity]
 * Tne maximum number of recursive calls this function is allowed to make
 * @param {Function} opts.getDirection 
 * The return value of this function determines the direction of the
 * current value in relation to the reference value:
 * - ` 0` - currentValue = referenceValue
 * - `-1` - currentValue < referenceValue
 * - `+1` - currentValue > referenceValue
 * 
 * It receives one argument representing the best guess for the target value
 * and is called once per iteration
 * @returns {{
 * value: Number,
 * steps: Number,
 * aborted: Boolean,
 * below: Boolean
 * }}
 * 
 * - `value` - The target value ± bias / 2
 * - `steps` - The amount of steps it needed to converge to `value`
 * - `aborted` - Whether or not the recursive loop was aborted due to reaching `maxSteps`
 * - `dir` - The direction of the current value in relation to the reference value (see `getDirection()`)
 */
export function binarySearch({
    min,
    max,
    bias = 1,
    round = false,
    maxSteps = Infinity,
    getDirection
})
{
    const mid = (min + max) / 2
    const value = round ? mid + 0.5 | 0 : mid

    const steps = arguments[1] || 0
    const abort = steps === maxSteps
    const dir = getDirection(value)

    if (abort || dir === 0 || max - min < bias)
    {
        return { value, steps, aborted: abort, dir }
    }
    else if (dir < 0)
    {
        arguments[0].min = mid

        return binarySearch(arguments[0], steps + 1)
    }
    else
    {
        arguments[0].max = mid

        return binarySearch(arguments[0], steps + 1)
    }
}

Examples:

Find the index for a value in a sorted array:

const arr = [ 23, 44, 67, 99, 109, 110, 304, 900, ... ]
const ref = 900

binarySearch({
    min: 0,
    max: arr.length-1,
    round: true,
    getDirection: v => arr[v] === ref ? 0 : arr[v] < ref ? -1 : 1
}) // --> { value: 7, steps: 3, aborted: false, dir: 0 }

Guess a number between 0 and 1 million:

const ref = 1337

binarySearch({
    min: 0,
    max: 1e6,
    round: true,
    getDirection: v => v === ref ? 0 : v < ref ? -1 : 1
}) // --> { value: 1337, steps: 18, aborted: false, dir: 0 }