首頁 > web前端 > js教程 > javascript折半查找詳解_javascript技巧

javascript折半查找詳解_javascript技巧

WBOY
發布: 2016-05-16 16:17:59
原創
1850 人瀏覽過

折半查找法

在有序表中,把待查找資料值與查找範圍的中間元素值比較,會有三種情況出現:

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     { 
        mid = (beg last) / 2; 
        if (x == data[mid] ) 
        { 
            return mid; 
        } 
        else if (data[mid]         { 
            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     { 
        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     int siz = sizeof(data1)/sizeof(int); 
    for (int i = 0; i     { 
        data1[i] = i; 
        cout     } 
    cout     int index = -1; 
    //index = BiSearch(data1, no2search, 0, siz); 
    index = IterBiSearch(data1, no2search, 0, siz); 
    cout     getchar(); 
    return 0; 

複製程式碼程式碼如下:

/**
  * 折半查找字元在陣列中的位置(有序列表)
  * @param array 擷取的陣列
  * @param x  要找的字元
  * @returns 字元在陣列中的位置,找不到回傳-1 
 */ 
函數binarySearch(數組,x){
  var lowPoint=1;                    
 var higPoint=array.length;
 var 回傳值=-1;               
 var midPoint;
 var 發現=假;                  
 while ((lowPoint   midPoint=Math.ceil((lowPoint higPoint)/2);
  //console.log(lowPoint "====" midPoint "====" higPoint);
  if(x>array[midPoint-1]){
   低點=中點1;
  }
  else if(x    higPoint= midPoint-1;
  }
  else if(x=array[midPoint-1]){
   發現=真;
  }
 }
 如果(找到){
    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'));
相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板