怎么在JavaScript中實現折半查找算法

本篇文章為大家展示了怎么在JavaScript中實現折半查找算法，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

一、問題描述：

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

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);//比最小的值還小，返回"您查找的數值不存在"
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時，整個函數都結束了，后面語句是不會執行的。

上述內容就是怎么在JavaScript中實現折半查找算法，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。