binarysearch (original) (raw)

1.0.1 • Public • Published 5 years ago

• Readme
• Code Beta
• 0 Dependencies
• 29 Dependents
• 13 Versions

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

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

search with user defined comparator 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

find first key that matches

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

find last key that matches

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

find closest key to where or key of searched value in the array

• if the key is in the array the key will point to
  • the first key that has that value by default
  • the last key that has that value if {end:true} option is specified
• only returns -1 if array is empty

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

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

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

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

bs.closest([1,2,4,5,5,5,6],5,{end:true}) === 5

query for rangeValue (inclusive). returns sliced values.

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

or simply access the array offsets directly as [start,end]

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

insert a value into a sorted array.

var arr = [1,3,4];

bs.insert(arr,2) === 1

arr[1] === 2

when you insert values and there are duplicates the default behavior is to insert the new value after the other same values. if you pass option.unique = true the key's value is replaced with the new value

var arr = [1,2,3];

bs.insert(arr,2)

var arr = [1,2,3];

bs.insert(arr,2,{unique:true});

insert with user defined comparator function

var arr = [5,6,7,8,9];

bs.insert(arr,10,function(value,add){

  if(value > add) return 1;

  else if(value < add) return -1;

  return 0;

});

create an object index

var index = bs.indexObject({a:2,b:1});

search an object index

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;

});

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