lower-bound.ts

// Port of lower_bound from https://en.cppreference.com/w/cpp/algorithm/lower_bound
// Used to compute insertion index to keep queue sorted after insertion
export default function lowerBound<T>(array: readonly T[], value: T, comparator: (a: T, b: T) => number): number {
    let first = 0
    let count = array.length

    while (count > 0) {
        const step = Math.trunc(count / 2)
        let it = first + step

        if (comparator(array[it], value) <= 0) {
            first = ++it
            count -= step + 1
        } else {
            count = step
        }
    }

    return first
}