quantile_rank_sorted.js

/* eslint no-bitwise: 0 */

/**
 * 本函数计算给定值在已排序数组中的分位数排名。通过二分查找算法，可在对数时间内完成计算。
 *
 * @param {Array<number>} x 已排序输入数组
 * @param {number} value 目标数值
 * @returns {number} 分位数排名（范围[0,1]）
 * @example
 * quantileRankSorted([1, 2, 3, 4], 3); // => 0.75
 * quantileRankSorted([1, 2, 3, 3, 4], 3); // => 0.7
 * quantileRankSorted([1, 2, 3, 4], 6); // => 1
 * quantileRankSorted([1, 2, 3, 3, 5], 4); // => 0.8
 */
function quantileRankSorted(x, value) {
    // 处理边界情况：值小于数组最小值
    if (value < x[0]) {
        return 0;
    }

    // 处理边界情况：值大于数组最大值
    if (value > x[x.length - 1]) {
        return 1;
    }

    // 获取目标值在数组中的下界索引
    let l = lowerBound(x, value);

    // 值不存在于数组中时直接返回比例位置
    if (x[l] !== value) {
        return l / x.length;
    }

    l++;

    // 获取目标值在数组中的上界索引
    const u = upperBound(x, value);

    // 唯一存在情况：上下界索引重合
    if (u === l) {
        return l / x.length;
    }

    /*
     * 计算包含目标值的连续索引范围的平均位置：
     * 1. 计算连续索引的数量（r = 范围长度）
     * 2. 使用等差数列求和公式计算总位置和
     * 3. 求平均位置后转换为比例值
     */
    const r = u - l + 1;
    const sum = (r * (u + l)) / 2; // 等差数列求和公式
    const mean = sum / r; // 计算平均位置

    return mean / x.length;
}

/**
 * 二分查找下界索引（第一个大于等于目标值的位置）
 * @param {Array<number>} x 已排序数组
 * @param {number} value 目标值
 * @returns {number} 下界索引
 */
function lowerBound(x, value) {
    let mid = 0;
    let lo = 0;
    let hi = x.length;

    while (lo < hi) {
        mid = (lo + hi) >>> 1; // 无符号右移实现取整

        if (value <= x[mid]) {
            hi = mid; // 向左收缩范围
        } else {
            lo = -~mid; // 等价于 mid + 1（位运算技巧）
        }
    }

    return lo;
}

/**
 * 二分查找上界索引（第一个大于目标值的位置）
 * @param {Array<number>} x 已排序数组
 * @param {number} value 目标值
 * @returns {number} 上界索引
 */
function upperBound(x, value) {
    let mid = 0;
    let lo = 0;
    let hi = x.length;

    while (lo < hi) {
        mid = (lo + hi) >>> 1; // 无符号右移实现取整

        if (value >= x[mid]) {
            lo = -~mid; // 等价于 mid + 1（位运算技巧）
        } else {
            hi = mid; // 向右收缩范围
        }
    }

    return lo;
}

export default quantileRankSorted;