首页 > 语言 > JavaScript > 正文

javascript折半查找详解

2024-05-06 16:15:16
字体:
来源:转载
供稿:网友
这篇文章主要介绍了javascript折半查找详解的相关资料,需要的朋友可以参考下
 

折半查找法

在有序表中,把待查找数据值与查找范围的中间元素值进行比较,会有三种情况出现:

1)     待查找数据值与中间元素值正好相等,则放回中间元素值的索引。

2)     待查找数据值比中间元素值小,则以整个查找范围的前半部分作为新的查找范围,执行1),直到找到相等的值。

3)     待查找数据值比中间元素值大,则以整个查找范围的后半部分作为新的查找范围,执行1),直到找到相等的值

4)     如果最后找不到相等的值,则返回错误提示信息。

按照二叉树来理解:中间值为二叉树的根,前半部分为左子树,后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下,约为

log2(n+1)-1

 

复制代码代码如下:

//Data为要查找的数组,x为待查找数据值,beg为查找范围起始,last为查找范围终止  
//非递归法  
int BiSearch(int data[], const int x, int beg, int last)  
{  
    int mid;//中间位置  
    if (beg > last)  
    {  
        return -1;  
    }  
    while(beg <= last)  
    {  
        mid = (beg + last) / 2;  
        if (x == data[mid] )  
        {  
            return mid;  
        }  
        else if (data[mid] < x)  
        {  
            beg = mid + 1;  
        }  
        else if (data[mid] > x)  
        {  
            last = mid - 1;  
        }  
    }  
    return -1;  
}  
//递归法  
int IterBiSearch(int data[], const int x, int beg, int last)  
{  
    int mid = -1;  
    mid = (beg + last) / 2;  
    if (x == data[mid])  
    {  
        return mid;  
    }  
    else if (x < data[mid])  
    {  
        return IterBiSearch(data, x, beg, mid - 1);  
    }  
    else if (x > data[mid])  
    {  
        return IterBiSearch(data, x, mid + 1, last);  
    }  
    return -1;  
}  
//主函数  
int _tmain(int argc, _TCHAR* argv[])  
{  
    int data1[60] = {0};  
    int no2search = 45;  
    cout << "The array is : " << endl;  
    int siz = sizeof(data1)/sizeof(int);  
    for (int i = 0; i < siz; i++)  
    {  
        data1[i] = i;  
        cout << data1[i] << " ";  
    }  
    cout << endl;  
    int index = -1;  
    //index = BiSearch(data1, no2search, 0, siz);  
    index = IterBiSearch(data1, no2search, 0, siz);  
    cout << "Index of " << no2search << " is " << index << endl;  
    getchar();  
    return 0;  
}  

 

 

复制代码代码如下:

/**
  * 折半查找字符在数组中的位置(有序列表)
  * @param array 被检索的数组
  * @param x  要查找的字符
  * @returns 字符在数组中的位置,没找到返回-1  
  */  
function binarySearch(array,x){ 
  var lowPoint=1;                     
 var higPoint=array.length;
 var returnValue=-1;                
 var midPoint;
 var found=false;                   
 while ((lowPoint<=higPoint)&&(!found)){
  midPoint=Math.ceil((lowPoint+higPoint)/2); 
  //console.log(lowPoint+"===="+midPoint+"===="+higPoint);
  if(x>array[midPoint-1]){
   lowPoint=midPoint+1;
  }
  else if(x<array[midPoint-1]){
   higPoint= midPoint-1;
  }
  else if(x=array[midPoint-1]){
   found=true;
  }
 } 
 if(found){
    returnValue=midPoint;
 }
 return returnValue;
}
/*var array2=[1,2,3,4,5,6,7,8,9,100,109];*/
var array2=['a','b','c','d','e','f','g'];
console.log(binarySearch(array2,'c'));

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表

图片精选