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

成都創(chuàng)新互聯(lián)成立于2013年，我們提供高端重慶網(wǎng)站建設公司、成都網(wǎng)站制作、網(wǎng)站設計、網(wǎng)站定制、網(wǎng)絡營銷推廣、小程序制作、微信公眾號開發(fā)、seo優(yōu)化服務，提供專業(yè)營銷思路、內容策劃、視覺設計、程序開發(fā)來完成項目落地，為房屋鑒定企業(yè)提供源源不斷的流量和訂單咨詢。

一、問題描述：

在一個升序數(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小，因而應該在右子數(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ù)組中間索引位置的值比要查找的值大，就轉而在數(shù)組中間位置之前的子數(shù)組中查找；相反，如果數(shù)組中間索引位置的值比要查找的值大，就轉而在數(shù)組中間位置之后的子數(shù)組中查找；如果數(shù)組中間索引位置的值恰好等于要查找的值，就返回該索引位置。

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

3、while中的邏輯說明：

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

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

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

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

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

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

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

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

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

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

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

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

上述內容就是怎么在JavaScript中實現(xiàn)折半查找算法，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

分享標題：怎么在JavaScript中實現(xiàn)折半查找算法-創(chuàng)新互聯(lián)
文章來源：http://www.sd-ha.com/article4/dgjpoe.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、網(wǎng)站制作、網(wǎng)站策劃、動態(tài)網(wǎng)站、品牌網(wǎng)站設計、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)