Maison >interface Web >js tutoriel >Explication détaillée de la méthode de mise en œuvre de la demi-recherche dans la recherche de tableau JS

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

黄舟
黄舟original
2017-03-27 14:39:071379parcourir

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 b078b0fb9960654bae9058be5faaef5d 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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn