1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/* eslint no-bitwise: 0 */
/** * This function returns the quantile in which one would find the given value in * the given array. With a sorted array, leveraging binary search, we can find * this information in logarithmic time. * * @param {Array<number>} x input * @returns {number} value value * @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) {    // Value is lesser than any value in the array    if (value < x[0]) {        return 0;    }
    // Value is greater than any value in the array    if (value > x[x.length - 1]) {        return 1;    }
    let l = lowerBound(x, value);
    // Value is not in the array    if (x[l] !== value) {        return l / x.length;    }
    l++;
    const u = upperBound(x, value);
    // The value exists only once in the array    if (u === l) {        return l / x.length;    }
    // Here, we are basically computing the mean of the range of indices    // containing our searched value. But, instead, of initializing an    // array and looping over it, there is a dedicated math formula that    // we apply below to get the result.    const r = u - l + 1;    const sum = (r * (u + l)) / 2;    const mean = sum / r;
    return mean / x.length;}
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;        }    }
    return lo;}
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;        } else {            hi = mid;        }    }
    return lo;}
export default quantileRankSorted;