Explication détaillée de la méthode de mise en œuvre de la demi-recherche dans la recherche de tableau JS

Cet article présente principalement la méthode d'implémentation de la demi-recherche dans JSarraysearch, et analyse le principe de l'algorithme de demi-recherche de tableau javascript en combinaison avec des Exemples. Compétences de mise en œuvre et Notes associées, les amis dans le besoin peuvent se référer à

Cet article décrit la méthode de mise en œuvre de la demi-recherche pour la recherche de tableau JS. Partagez-le avec tout le monde pour votre référence, comme suit :

1. Principe de la méthode :

Lors de la recherche d'une valeur spécifique à partir d'un tableau de séquence donné arr Quand déterminer un point intermédiaire milieu = Math.floor((point final - point de départ) / 2);

3. Sous le principe de startIndex < endIndex, comparez la taille de arr[middle] et value:

(1) arr[middle] < value

Ajustez la plage de recherche à la seconde moitié du tableau, c'est-à-dire startIndex = middle + 1, endIndex = arr.length -1;

(2) arr[middle] > value

Ajustez la plage de recherche à la première moitié du tableau, c'est-à-dire startIndex = 0, endIndex = middle - 1;

Ensuite, recalculez le milieu et comparez à nouveau arr[middle] et value, jusqu'à ce qu'ils soient égaux ou startIndex >= endIndex.

2. Code :

3. Avantages et inconvénients :

// 该例的写法适用于序列为由小到大的数组
function binarySearch(arr, value) {
  var startIndex = 0,
  endIndex = arr.length - 1;
  middle = Math.floor((endIndex - startIndex) / 2);
  while (arr[middle] !== value && startIndex < endIndex) {
    if (arr[middle] > value) {
      endIndex = middle - 1;
    } else if (arr[middle] < value) {
      startIndex = middle + 1;
    }
    middle = Math.floor((endIndex - startIndex) / 2);
  }
  return (arr[middle] !== value) ? -1 : middle;
}

(1) Avantages : À chaque recherche, le nombre d'éléments du tableau à rechercher sera réduit de moitié , ses performances sont donc meilleures que la méthode de recherche linéaire (dans les éléments du tableau, c'est particulièrement évident lorsqu'il y en a plus);

(2) Inconvénients :

ne s'applique qu'aux tableaux de séquences. Avant d'utiliser la méthode

sur des tableaux

ordinaires, le tableau doit être trié

.

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!