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