binarysearch

binarysearch

pure js binary search for sorted javascript arrays||array like objects. returns any || last || first || closest matched key for value, or slice between 2 values where values need not exist.

returns the matched key or -1 if not found.

example

var bs = require('binarysearch');

bs([1,4,7,9,22,100,1000],7) === 2
//true

bs([1],5) === -1
// true

search with user defined comparitor function

bs([5,6,7,8,9],9,function(value,find){
  if(value > find) return 1;
  else if(value < find) return -1;
  return 0;
}) === 4
// true

find first key that matches

bs.first([0,1,2,3,3,3,4],3) === 2

find last key that matches

bs.last([,1,2,3,3,3,4],3) === 4
 

find closest key to search value

• if the value is in the array it returns the first index with that value in the array
• if the value is not the index in the array of the closest item that sorts immediately before this item will be returned.
  • +1 is the index where you should set this item into the array if you want to add it.
  • if index 0 is the closest match -i will be returmed.

bs.closest([1,2,4,5,6],3) === 1
bs.closest([1,2,4,5,6],0) === -1
bs.closest([1,2,4,5,6],200) === 6

query for range (inclusive)

bs.range([1,2,3,3,3,4,4,6],3,5) === [3,3,3,4,4]

search with object index

var index = bs.indexObject({a:2,b:1});
// [{k:'b',v:1},{k:a,v:2}];

var obj = {a:{id:22,name:'bob'},b:{id:11,name:'joe'}};
index = bs.indexObject(obj,function(o1,o2){
  if(o1.id > o2.id) return 1
  else if(o1.id < o2.id) return -1;
  return 0; 
});
// [{k:'b',v:11},{k:a,v:22}];


obj[bs(index,'bob').k] === {id:22,name:'bob'};

thanks

@rvagg https://github.com/rvagg for making leveldb bindings for node these search functions emulate leveldb query behavior.