UNPKG

721 BPlain TextView Raw
1import id from './_id';
2import cmp from './_cmp';
3import type {compareFn, mapFn} from './_types';
4
5/**
6 * Binary searches value in sorted array.
7 * @param x an array (sorted)
8 * @param v search value
9 * @param fc compare function (a, b)
10 * @param fm map function (v, i, x)
11 * @returns index of value | ~(index of closest value)
12 */
13function bsearchAny<T, U=T>(x: T[], v: T, fc: compareFn<T|U>=null, fm: mapFn<T, T|U>=null): number {
14 var fc = fc||cmp, fm = fm||id;
15 var v1 = fm(v, 0, null);
16 for(var i=0, I=x.length; i<I;) {
17 var m = i+I >>> 1;
18 var u1 = fm(x[m], m, x);
19 var c = fc(u1, v1);
20 if(c<0) i = m+1;
21 else if(c>0) I = m;
22 else return m;
23 }
24 return ~i;
25}
26export default bsearchAny;