Austausch über den binären JS-Suchalgorithmus und -Code

Dieser Artikel teilt Ihnen hauptsächlich den binären JS-Suchalgorithmus und den Code mit. Freunde, die ihn benötigen, können darauf verweisen.

4.1 Binäre Suche
Einführung in den Algorithmus
Die binäre Suche, auch Halbsuche genannt, ist ein Suchalgorithmus zum Auffinden bestimmter Elemente in einem geordneten Array. Der Suchvorgang kann in die folgenden Schritte unterteilt werden:
(1) Beginnen Sie zunächst mit der Suche ab dem mittleren Element des geordneten Arrays. Wenn das Element zufällig das Zielelement ist (d. h. das zu findende Element), Der Suchvorgang endet, andernfalls fahren Sie mit dem nächsten Schritt fort.
(2) Wenn das Zielelement größer oder kleiner als das mittlere Element ist, suchen Sie in der Hälfte des Arrays, die größer oder kleiner als das mittlere Element ist, und wiederholen Sie dann den ersten Schritt.
(3) Wenn das Array in einem bestimmten Schritt leer ist, bedeutet dies, dass das Zielelement nicht gefunden werden kann.
Referenzcode:
Nicht-rekursiver Algorithmus

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 返回目标元素的索引值

Rekursiver Algorithmus

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 返回目标元素的索引值

Das obige ist der detaillierte Inhalt vonAustausch über den binären JS-Suchalgorithmus und -Code. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!