Using JavaScript, how do I perform a binary search that will return multiple values?
Background
I currently have an array like this:
[1,1,2,3,4,5,5,5,6,7,8,8,8,8,9,10]
I am using the excellent JS Binary Search formula from this site :
searchArray = function(needle, haystack, case_insensitive) {
if (typeof(haystack) === 'undefined' || !haystack.length) return -1;
var high = haystack.length - 1;
var low = 0;
case_insensitive = (typeof(case_insensitive) === 'undefined' || case_insensitive) ? true:false;
needle = (case_insensitive) ? needle.toLowerCase():needle;
while (low <= high) {
mid = parseInt((low + high) / 2)
element = (case_insensitive) ? haystack[mid].toLowerCase():haystack[mid];
if (element > needle) {
high = mid - 1;
} else if (element < needle) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
};
This is great for returning a single value.
Question
How do I return a range and not a single value? For example, how could I return all values 8
from an array, but STILL uses a binary search (I don't want to iterate over everything!).
Thank!
source to share
Something like that? http://jsfiddle.net/DCLey/3/
var arr = ['1','1','2','3','4','5','5','5','6','7','8','8','8','8','9','10'];
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
var searchArray = function(needle, haystack, case_insensitive) {
if (typeof(haystack) === 'undefined' || !haystack.length) return -1;
var high = haystack.length - 1;
var low = 0;
var vals = [];
var bUp = true;
var bDown = true;
var i = 1;
case_insensitive = (typeof(case_insensitive) === 'undefined' || case_insensitive) ? true:false;
needle = (case_insensitive) ? needle.toLowerCase():needle;
while (low <= high) {
mid = parseInt((low + high) / 2)
element = (case_insensitive) ? haystack[mid].toLowerCase():haystack[mid];
if (element > needle) {
high = mid - 1;
} else if (element < needle) {
low = mid + 1;
} else {
vals.push(mid);
while(bUp || bDown){
if(bUp && haystack[mid] === haystack[mid + i]){
vals.push(mid + i);
}else{
bUp = false;
}
if(bDown && haystack[mid] === haystack[mid - i]){
vals.push(mid - i);
}else{
bDown = false;
}
i++;
}
return vals;
}
}
return -1;
};
alert(searchArray('8', arr, true));
source to share
If you just don't want to count the number of instances of a given number, you need to return the superscripts and subscripts of the number in the array. We can choose one of two approaches:
- Write a binary search that returns the indices of the upper and lower bounds as an array
- Stick to the standard binary search, which returns the lower bound, and then just iterate until we reach the end of the run.
Taking Approach 2 is slightly less revealing, but retains the general algorithm.
source to share