javascript折半查找詳解

更新時(shí)間：2015年01月26日 10:07:21 投稿：hebedich

這篇文章主要介紹了javascript折半查找詳解的相關(guān)資料,需要的朋友可以參考下

折半查找法：

在有序表中，把待查找數(shù)據(jù)值與查找范圍的中間元素值進(jìn)行比較，會(huì)有三種情況出現(xiàn)：

1）待查找數(shù)據(jù)值與中間元素值正好相等，則放回中間元素值的索引。

2）待查找數(shù)據(jù)值比中間元素值小，則以整個(gè)查找范圍的前半部分作為新的查找范圍，執(zhí)行1），直到找到相等的值。

3）待查找數(shù)據(jù)值比中間元素值大，則以整個(gè)查找范圍的后半部分作為新的查找范圍，執(zhí)行1），直到找到相等的值

4）如果最后找不到相等的值，則返回錯(cuò)誤提示信息。

按照二叉樹來理解：中間值為二叉樹的根，前半部分為左子樹，后半部分為右子樹。折半查找法的查找次數(shù)正好為該值所在的層數(shù)。等概率情況下，約為

log2(n+1)-1

復(fù)制代碼代碼如下:

//Data為要查找的數(shù)組，x為待查找數(shù)據(jù)值，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;  

}  

//主函數(shù)  

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;  

}

復(fù)制代碼代碼如下:

/**

  * 折半查找字符在數(shù)組中的位置(有序列表)

  * @param array 被檢索的數(shù)組

  * @param x  要查找的字符

  * @returns 字符在數(shù)組中的位置，沒找到返回-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'));