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

一、問題描述：

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

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

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

二、我的實現

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 "您查找的數不存在";    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、基本思路：

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

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

3、while中的邏輯說明：

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

（2）循環結束條件：

a、一旦當right小于0時，就不再查找，再糾纏也不會有結果。例如：在a=[1,2,3,4,5,6,7,8,9]中查找0，當查找范圍變為left=0,right=0,center=0時，進入while語句，由于arr[center]>0,故執行

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

得到right=-1此時應不再進入循環；

b、一旦當left>l-1時，就不再查找，同樣再糾纏也不會有結果。例如：在a=[1,2,3,4,5,6,7,8,9]中查找10，當查找范圍變為left=8,right=8,center=8時，進入while語句，由于arr[center]<10,故執行

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

得到left=9,此時應不再進入循環；

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

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

6、當left==right了，而arr[center]==num卻沒執行，可以得出結論查找不到的；

7、當arr[center]==num時，整個函數都結束了，后面語句是不會執行的。

上述代碼使用在線HTML/CSS/JavaScript代碼運行工具http://tools.VeVB.COm/code/HtmlJsRun測試運行結果如下：

更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》

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