BINARY SEARCH This Javascript Binary Search becomes very useful when large arrays are used. The developed Binary Search algorithm handles mixed numerical-alphabetic array data - a simple array or an array of arrays. It optionally returns the first instance of a target value, permitting one to iterate up through the other instances of that value. For a binary search, a sorted array is necessary. See the SortIt() function for a solution sorting mixed numerical & alphabetic data. Note: this Binary search was designed to properly handle data ordered by SortIt, which puts numerical data first in the order, followed by all the alpha data (or alph-numerical data, e.g., 'TY6VB98'). Sort the array (or array of arrays) on the column in which you want to find the value (or the first instance of such value). The algorithm below uses the following:
val = value to be found, TheArr = array to be searched,
col = column or second index, eg, TheArr[0][5] is col==5 (the sixth)
If you put col==-1, then you're defining that TheArr is not an array of arrays, but a simple array.
If you put series==0 then the function will find one value & do no more.
But if series==1 then it will bubble down from the first found to find first instance of 'val' and return that index.
The function returns the index if found or (-1) if not found.
function BinSearch(val,TheArr,col,series){
var index=-2;
var Lo=ans=mid=0;
var x='';
var Hi=TheArr.length;
while (index==-2) {
mid = Math.floor((Lo+Hi)/2);
if(col==-1){x=TheArr[mid];}
else {x=TheArr[mid][col];}
if(val==x){index=mid;}
else{if((mid==Hi)||(mid==Lo)){index=-1;}
else{
if (isNaN(val-x)){
if((isNaN(val))&&(isNaN(x))){ans=(val<x);}
else {ans=(isNaN(val)?false:true);}
}
else {ans=(val<x);}
if(ans==true){Hi=mid;}
else{Lo=mid;}
}
}
}
if(index==0){return index;}
if ((series==1)&&(index>=0)){
if (col==-1){x=TheArr[index];}
else {x=TheArr[index][col];}
while ((x==val)&&(index>0)){
index--;
if (col==-1){x=TheArr[index];}
else {x=TheArr[index][col];}
}
if(x==val){return index;}
index++;
}
return index;
}  Top
| 