methods/bsearchIndex/index.js

/**
 *  By using binary search, finds an index of a value from this array which
 *  meets the given condition in **`O(log n)`** where `n` is the length of the
 *  array.
 *
 *  You can use this method in two modes: a **find-minimum mode** and a
 *  **find-any mode**. In either case, the elements of the array must be
 *  monotone (or sorted) with respect to the given callback.
 *
 *  In **find-minimum mode** (this is a good choice for typical use cases), the
 *  callback must always return `true` or `false`, and there must be an index
 *  **`i`** `(0 <= i <= array.length)` so that:
 *  - the callback returns `false` for any element whose index is less
 *      than `i`, and
 *  - the callback returns `true` for any element whose index is greater
 *      than or equal to `i`.
 *
 *  This method returns the index `i`. If i is equal to `array.length`, it
 *  returns `null`.
 *
 *  In **find-any mode**, the callback must always return a number, and there
 *  must be two indices **`i`** and **`j`** `(0 <= i <= j <= array.length)`
 *  so that:
 *  - the callback returns a positive number if `0 <= k < i`,
 *  - the callback returns zero if `i <= k < j`, and
 *  - the callback returns a negative number if `j <= k < array.length`.
 *
 *  Under this condition, this method returns any index within `i...j`.
 *  If `i` is equal to `j` (i.e., there is no element that satisfies the
 *  callback), this method returns `null`.
 *
 *  You must not mix the two modes at a time; the block must always return
 *  either `true`/`false`, or always return a number. It is undefined which
 *  value is actually picked up at each iteration.
 *
 *  @param {Array} array
 *  @param {Function} callback - This should return a boolean for
 *      **find-minimum mode**, and a number for **find-any mode**.
 *
 *  @return {number} The corresponding index an element that satisfies the
 *      given callback.
 *
 *  @example
 *  bsearchIndex([0, 4, 7, 10, 12], x => x >= 4); // => 1
 *  bsearchIndex([1, 2, 3, 4, 5], x => 2 - x); // => 1
 *
 *  @example
 *  rbjs([0, 4, 7, 10, 12]).bsearchIndex(x => x >= 4); // => 1
 *  rbjs([1, 2, 3, 4, 5]).bsearchIndex(x => 2 - x); // => 1
 */
export default function bsearchIndex(array, callback) {
    const [i, j] = (function search(arr, cb, _i, _j) {
        if (arr.length === 0) {
            return [_i, _j];
        }

        const idx = Math.floor(arr.length / 2);
        const result = cb(arr[idx]);

        if (result === true) {
            // Find-minimum mode: traverse left subtree
            return search(arr.slice(0, idx), cb, _i, _j);
        } else if (result === false) {
            // Find-minimum mode: traverse right subtree
            return search(arr.slice(idx + 1), cb, _i + idx + 1, _j);
        } else if (result < 0) {
            // Find-any mode: traverse left subtree
            return search(arr.slice(0, idx), cb, Math.min(_i, idx), idx);
        } else if (result > 0) {
            // Find-any mode: traverse right subtree
            return search(arr.slice(idx + 1), cb, (_i += idx + 1), Math.max(_j, _i));
        }
        // Find-any mode: return the index of any item that makes the given
        // callback return 0.
        return [(_i += idx), _j];
    })(array, callback, 0, -1);

    // Find-minimum mode: return null if i === array.length
    // Find-any mode: return null if i === j
    return i === array.length || i === j ? null : i;
}