1 | ;
|
2 |
|
3 | /**
|
4 | * Gives same value.
|
5 | * @param v a value
|
6 | * @returns v
|
7 | */
|
8 | function id(v) {
|
9 | return v;
|
10 | }
|
11 |
|
12 | /**
|
13 | * Compares two values.
|
14 | * @param a a value
|
15 | * @param b another value
|
16 | * @returns a<b: -1, a=b: 0, a>b: 1
|
17 | */
|
18 | function cmp(a, b) {
|
19 | return a < b ? -1 : (a > b ? 1 : 0);
|
20 | }
|
21 |
|
22 | /**
|
23 | * Binary searches value in sorted array.
|
24 | * @param x an array (sorted)
|
25 | * @param v search value
|
26 | * @param fc compare function (a, b)
|
27 | * @param fm map function (v, i, x)
|
28 | * @returns index of value | ~(index of closest value)
|
29 | */
|
30 | function bsearchAny(x, v, fc = null, fm = null) {
|
31 | var fc = fc || cmp, fm = fm || id;
|
32 | var v1 = fm(v, 0, null);
|
33 | for (var i = 0, I = x.length; i < I;) {
|
34 | var m = i + I >>> 1;
|
35 | var u1 = fm(x[m], m, x);
|
36 | var c = fc(u1, v1);
|
37 | if (c < 0)
|
38 | i = m + 1;
|
39 | else if (c > 0)
|
40 | I = m;
|
41 | else
|
42 | return m;
|
43 | }
|
44 | return ~i;
|
45 | }
|
46 |
|
47 | module.exports = bsearchAny;
|