javascript - Find closest nodes in binary search tree -

i want have collection of objects, sorted numerical property, val. want able retrieve objects matching val matches value, say, x, or if no objects exist property val matching x, find objects nearest val above , below x. (multiple objects may have same values val)

one of few bst libraries i've found dsjslib. has calls treemultimap holds multiple values single key. problem can't see how retrieve nodes closest x if there no exact matches.

how might go this? browser support es6 seems coming long way, perhaps use map this?

this sounds after binary search. had developed binary findindex method arrays works in sorted arrays of course. takes callback , of sorted array of objects can searched. since binary search faster standard findindex or indexof methods.

the default callback x => x makes handle sorted primitives default if no callback provided. it's current state if finds searched object returns it's index if not return -1. if searched can modified return indices of proximity. can add later if require.

array.prototype.sortedfindindex = function(val, cb = x => x) { // default callback primitive arrays    var deli = this.length-1,                                    // delta index        base = 0;                                                // base add delta index    while (deli > 0 && cb(this[base + deli]) != val) {      deli = ~~(deli/2);      cb(this[base + deli]) < val && (base += deli);    }    return cb(this[base + deli]) === val ? base + deli : -1;  };    arr = [{a:0,b:"foo"},{a:1,b:"bar"},{a:2,b:"baz"},{a:3,b:"qux"},{a:4,b:"fox"},{a:5,b:"pun"},{a:6,b:"alf"}],  idx = arr.sortedfindindex(4, o => o.a);    console.log(idx);

and here modified version handles failure cases more cleverly. if searched item can not found, following snippet return negated value of index should have existed. tricky part. return negative 0 (-0) if missing item should inserted @ index 0. should piece of cake find upper , lower proximity of non existent item.

array.prototype.sortedfindindex = function(val, cb = x => x) { // default callback primitive arrays    var            deli = this.length-1,                         // delta index                   base = 0,                                     // base add delta index        calculatedvalue = cb(this[base + deli]),                 // use callback , value             expectedat = => { while (this[i] !== void 0 && cb(this[i]) < val) ++i;                                 return -i};    while (deli > 0 && calculatedvalue != val) {      deli = ~~(deli/2);      (calculatedvalue = cb(this[base + deli])) < val && (base += deli);    }    return calculatedvalue === val ? base + deli : expectedat(base + deli);  };    arr = [{a:0,b:"foo"},{a:1,b:"bar"},{a:2,b:"baz"},{a:3,b:"qux"},{a:4,b:"fox"},{a:5,b:"pun"},{a:6,b:"alf"},{a:7,b:"alf"},{a:8,b:"alf"},{a:9,b:"alf"},{a:10,b:"alf"},{a:11,b:"alf"},{a:13,b:"alf"}],  idx = arr.sortedfindindex(12, o => o.a);    console.log(idx);