首頁  >  文章  >  web前端  >  關於JS二分查找演算法及程式碼的分享

關於JS二分查找演算法及程式碼的分享

零到壹度
零到壹度原創
2018-03-20 11:20:521531瀏覽

本文主要和大家分享JS二分查找演算法及程式碼,需要的朋友可以參考下,希望能幫助大家。

4.1 二分查找
演算法介紹
二分法查找,也稱為折半查找,是一種在有序數組中查找特定元素的搜尋演算法。查找過程可以分為以下步驟:
(1)首先,從有序數組的中間的元素開始搜索,如果該元素正好是目標元素(即要查找的元素),則搜索過程結束,否則進行下一步。
(2)如果目標元素大於或小於中間元素,則在陣列大於或小於中間元素的那一半區域查找,然後重複第一步的操作。
(3)如果某一步陣列為空,則表示找不到目標元素。
參考程式碼:
非遞迴演算法

function binary_search(arr,key){
  var low=0,
  high=arr.length-1;
  while(low<=high){
     var mid=parseInt((high+low)/2);
     if(key==arr[mid]){
        return mid;
     }else if(key>arr[mid]){
        low=mid+1;
     }else if(key<arr[mid]){
        high=mid-1;
    }else{
      return -1;
    }
  }
};
var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result=binary_search(arr,10);
alert(result); //  9 返回目标元素的索引值

#遞迴演算法

function binary_search(arr,low,high,key){
  if(low>high){
    return -1;   
  }
  var mid=parseInt((high+low)/2);
  if(arr[mid]==key){
    return mid;
  }else if(arr[mid]>key){
    high=mid-1;
    return binary_search(arr,low,high,key);
  }else if(arr[mid]<key){
    low=mid+1;
    return binary_search(arr,low,high,key);
  }
};
var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result=binary_search(arr,0,13,10);
alert(result); // 9 返回目标元素的索引值

以上是關於JS二分查找演算法及程式碼的分享的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn