Partage sur l'algorithme et le code de recherche binaire JS

Cet article partage principalement avec vous l'algorithme et le code de recherche binaire JS. Les amis qui en ont besoin peuvent s'y référer. J'espère qu'il pourra aider tout le monde.

4.1 Recherche binaire
Introduction à l'algorithme
La recherche binaire, également appelée demi-recherche, est un algorithme de recherche permettant de trouver des éléments spécifiques dans un tableau ordonné. Le processus de recherche peut être divisé en les étapes suivantes :
(1) Commencez par commencer la recherche à partir de l'élément du milieu du tableau ordonné. Si l'élément se trouve être l'élément cible (c'est-à-dire l'élément à trouver), le processus de recherche se termine, sinon passez à l'étape suivante.
(2) Si l'élément cible est supérieur ou inférieur à l'élément du milieu, recherchez dans la moitié du tableau qui est supérieure ou inférieure à l'élément du milieu, puis répétez la première étape.
(3) Si le tableau à une certaine étape est vide, cela signifie que l'élément cible est introuvable.
Code de référence :
Algorithme non récursif

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

Algorithme récursif

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!