javascript折半查找详解
折半查找法：
在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：
1） 待查找数据值与中间元素值正好相等，则放回中间元素值的索引。
2） 待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。
3） 待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值
4） 如果最后找不到相等的值，则返回错误提示信息。
按照二叉树来理解：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为
log2(n+1)-1
//Data为要查找的数组，x为待查找数据值，beg为查找范围起始，last为查找范围终止
//非递归法
intBiSearch(intdata[],constintx,intbeg,intlast)
{
intmid;//中间位置
if(beg>last)
{
return-1;
}
while(beg<=last)
{
mid=(beg+last)/2;
if(x==data[mid])
{
returnmid;
}
elseif(data[mid]<x)
{
beg=mid+1;
}
elseif(data[mid]>x)
{
last=mid-1;
}
}
return-1;
}
//递归法
intIterBiSearch(intdata[],constintx,intbeg,intlast)
{
intmid=-1;
mid=(beg+last)/2;
if(x==data[mid])
{
returnmid;
}
elseif(x<data[mid])
{
returnIterBiSearch(data,x,beg,mid-1);
}
elseif(x>data[mid])
{
returnIterBiSearch(data,x,mid+1,last);
}
return-1;
}
//主函数
int_tmain(intargc,_TCHAR*argv[])
{
intdata1[60]={0};
intno2search=45;
cout<<"Thearrayis:"<<endl;
intsiz=sizeof(data1)/sizeof(int);
for(inti=0;i<siz;i++)
{
data1[i]=i;
cout<<data1[i]<<"";
}
cout<<endl;
intindex=-1;
//index=BiSearch(data1,no2search,0,siz);
index=IterBiSearch(data1,no2search,0,siz);
cout<<"Indexof"<<no2search<<"is"<<index<<endl;
getchar();
return0;
}
/**
*折半查找字符在数组中的位置(有序列表)
*@paramarray被检索的数组
*@paramx 要查找的字符
*@returns字符在数组中的位置，没找到返回-1
*/
functionbinarySearch(array,x){
varlowPoint=1;
varhigPoint=array.length;
varreturnValue=-1;
varmidPoint;
varfound=false;
while((lowPoint<=higPoint)&&(!found)){
midPoint=Math.ceil((lowPoint+higPoint)/2);
//console.log(lowPoint+"===="+midPoint+"===="+higPoint);
if(x>array[midPoint-1]){
lowPoint=midPoint+1;
}
elseif(x<array[midPoint-1]){
higPoint=midPoint-1;
}
elseif(x=array[midPoint-1]){
found=true;
}
}
if(found){
returnValue=midPoint;
}
returnreturnValue;
}
/*vararray2=[1,2,3,4,5,6,7,8,9,100,109];*/
vararray2=['a','b','c','d','e','f','g'];
console.log(binarySearch(array2,'c'));