本文實例講述了JavaScript折半查找（二分查找）算法原理與實現(xiàn)方法。分享給大家供大家參考，具體如下：

一、問題描述：

在一個升序數(shù)組中，使用折半查找得到要查詢的值的索引位置。如：

var a=[1,2,3,4,5,6,7,8,9];
search(a,3);//返回2
search(a,1);//左邊界，返回0
search(a,9);//右邊界，返回8
search(a,0);//比最小的值還小，返回"您查找的數(shù)值不存在"
search(a,10);//比最大的值還大，返回"您查找的數(shù)值不存在"

注：折半查找必須在有序數(shù)組中才有效，無序的數(shù)組不能實現(xiàn)查找功能。比如：在[10,5,6,7,8,9,20]中查找10，中間索引位置的值為7，比較得出7比10小，因而應(yīng)該在右子數(shù)組中查找，實際上不可能找到10；

二、我的實現(xiàn)

function search(arr,num) {
  var l=arr.length;
  var left=0;
  var right=l-1;
  var center=Math.floor((left+right)/2);
  while(left<=l-1&&right>=0){
    if (arr[center]==num) return center;
    if (left==right) return "您查找的數(shù)不存在";
    if (arr[center]>num) {
      right=center-1;
      center=Math.floor((left+right)/2);
    }else if (arr[center]<num) {
      left=center+1;
      center=Math.floor((left+right)/2);
    }
  }
}
var a=[1,2,3,4,5,6,7,8,9];
console.log(search(a,-2));

說明：

1、基本思路：

每次比較，如果數(shù)組中間索引位置的值比要查找的值大，就轉(zhuǎn)而在數(shù)組中間位置之前的子數(shù)組中查找；相反，如果數(shù)組中間索引位置的值比要查找的值大，就轉(zhuǎn)而在數(shù)組中間位置之后的子數(shù)組中查找；如果數(shù)組中間索引位置的值恰好等于要查找的值，就返回該索引位置。

2、left定義查找范圍的起始位置，right定義查找范圍的結(jié)束位置，center定義查找范圍的中間位置。

3、while中的邏輯說明：

（1）由于不知道具體查找查找多少次，while是比較好的選擇；

（2）循環(huán)結(jié)束條件：

a、一旦當(dāng)right小于0時，就不再查找，再糾纏也不會有結(jié)果。例如：在a=[1,2,3,4,5,6,7,8,9]中查找0，當(dāng)查找范圍變?yōu)?code>left=0,right=0,center=0時，進(jìn)入while語句，由于arr[center]>0,故執(zhí)行

right=center-1;
center=Math.floor((left+right)/2);

得到right=-1此時應(yīng)不再進(jìn)入循環(huán)；

b、一旦當(dāng)left>l-1時，就不再查找，同樣再糾纏也不會有結(jié)果。例如：在a=[1,2,3,4,5,6,7,8,9]中查找10，當(dāng)查找范圍變?yōu)?code>left=8,right=8,center=8時，進(jìn)入while語句，由于arr[center]<10,故執(zhí)行

left=center;
center=Math.floor((left+right)/2);

得到left=9,此時應(yīng)不再進(jìn)入循環(huán)；

4、始終是通過center匹配到要查找的值；

5、Math.floor處理了查找范圍長度為偶數(shù)的情況；

6、當(dāng)left==right了，而arr[center]==num卻沒執(zhí)行，可以得出結(jié)論查找不到的；

7、當(dāng)arr[center]==num時，整個函數(shù)都結(jié)束了，后面語句是不會執(zhí)行的。

上述代碼使用在線HTML/CSS/JavaScript代碼運行工具http://tools.jb51.net/code/HtmlJsRun測試運行結(jié)果如下：

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

最新評論