Skip to content

Instantly share code, notes, and snippets.

@kariudo
Last active August 29, 2015 14:00
Show Gist options
  • Save kariudo/11289179 to your computer and use it in GitHub Desktop.
Save kariudo/11289179 to your computer and use it in GitHub Desktop.
Binary Search sorted list object
function SortedList() {
this.length = 0;
this.list = [];
}
SortedList.prototype.add = function(val) {
this.list.splice(findSpot(this.list,val,this.length)+1,0,val);
this.length++;
}
SortedList.prototype.get = function(i) {
return this.list[i];
}
function findSpot(arr,val,len) {
var max = len-1;
var min = 0;
var pos;
if (arr == [] || len === 0) {
return 0;
}
if (val >= arr[len-1]) {
return max;
}
if (val <= arr[0]) {
return -1;
}
while(min!=max){
pos = Math.floor((min+max)/2);
if (val == arr[pos]) {
return pos;
}
if (val>arr[pos] && val < arr[pos+1]){
return pos;
}
if (val > arr[pos]){
min = pos;
} else {
max = pos;
}
}
return pos;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment