[RUBY] Utilisez la recherche binaire pour voir s'il y a des valeurs dans le tableau

C'est une histoire que beaucoup de gens ont déjà écrite, Je voudrais approfondir ma compréhension en écrivant, je vais donc l'écrire.

problème

Résolvons le problème suivant en utilisant la recherche binaire.

Il y a un tableau ʻarray = [1, 3, 5, 6, 9, 10, 13, 20, 26, 34] `, Écrivez du code pour savoir si une valeur existe dans ce tableau. Si aucune valeur n'existe dans le tableau, "La valeur n'existe pas dans le tableau" s'affiche et S'il existe, le numéro du tableau s'affiche.

#Exemple de sortie 1
Veuillez saisir le numéro que vous souhaitez rechercher
5
5 est le deuxième du tableau

#Exemple de sortie 2
Veuillez saisir le numéro que vous souhaitez rechercher
8
8 n'existe pas dans le tableau

Qu'est-ce que la recherche binaire en premier lieu?

Lorsque vous recherchez des listes triées ou des données dans des tableaux (en supposant qu'elles n'ont pas la même valeur) Regardez la valeur au centre et utilisez la relation de grandeur avec la valeur que vous souhaitez rechercher, Déterminez si la valeur que vous souhaitez rechercher se trouve à droite ou à gauche de la valeur centrale, Une méthode de recherche en s'assurant qu'elle n'existe pas d'un côté. Étant donné que les choix sont divisés par deux en un seul processus, on peut s'attendre à une amélioration de la vitesse de traitement. Également appelée recherche bipartite ou recherche bipartite.

J'écrirai à peu près à quoi ça ressemble

La valeur que vous souhaitez rechercher est «target», L'indice le plus à gauche est «gauche», L'indice le plus à droite est «right», L'indice au milieu est attribué à «centre».

Au fait, cette fois, nous chercherons avec target = 5.

La figure ci-dessous montre la disposition. SC1.png Essayons-le réellement.

Dans la première recherche left = 0 right = 9 Et l'indice avec la valeur centrale est center = (gauche + droite) / 2, c'est-à-dire centre = 4. (En fait, 9 divisé par 2 est 4,5, mais dans le cas de Ruby, entier / entier = entier (arrondi au nombre entier inférieur le plus proche), donc ce n'est pas grave) Maintenant que vous connaissez l'indice avec la valeur centrale, comparez-le à la valeur que vous souhaitez rechercher. array[center] = 9 target = 5 Donc, tableau [centre]> cible. Vous connaissez maintenant la plage de recherche suivante. Cela ressemble à la figure ci-dessous. Gray est hors de recherche. SC2.png Comme vous pouvez le voir sur la figure, les bons changements. Puisqu'il sera changé sur le côté gauche du centre right = center - 1

Bien sûr, le centre change également. La méthode de recherche est la même que la première fois. center = (left + right) / 2 À propos, la deuxième fois qu'il est calculé, centre = 1.

Ensuite, comme la première fois, comparez la valeur centrale avec la valeur que vous souhaitez rechercher. array[center] = 3 target = 5 Donc, tableau [centre] <cible.

Et vous pouvez voir la prochaine plage de recherche. SC3.png Cette fois, a laissé des changements. Parce que ce sera un droit du centre left = center + 1 Le centre change également. La méthode de recherche est la même qu'avant. center = (left + right) / 2 À propos, la troisième fois est calculée comme centre = 2.

Comparez ensuite la valeur centrale avec la valeur que vous souhaitez rechercher comme auparavant. array[center] = 5 target = 5 array [center] == target et la recherche se termine.

Exemple de réponse

Je vais le réécrire en organisant ce que j'ai écrit à peu près ci-dessus.

def binary_search(array, right, target)
  left = 0
  while left <= right
    center = (left + right) / 2
    if array[center] == target
      return center
    elsif array[center] > target
      right = center - 1
    else
      left = center + 1
    end
  end
  return -1 
end

array = [1, 3, 5, 6, 9, 10, 13, 20, 26, 34]  #16e ligne

puts "Veuillez saisir le numéro que vous souhaitez rechercher"  #18e ligne
target = gets.to_i
elements_num = array.count - 1

result = binary_search(array, elements_num, target)  #Ligne 22

if result == -1  #24e ligne
  puts "#{target}N'existe pas dans le tableau"
else
  puts "#{target}Est un tableau#{result}Existe en deuxième"
end

Supplément

Il existe une description de la recherche binaire dans la méthode binary_search.

Réglez pour répéter le traitement avec while. La condition pour que la répétition soit valide est jusqu'à ce que l'indice le plus à gauche (à gauche) du tableau devienne le même que l'indice le plus à droite (à droite) du tableau (lorsqu'il dépasse, le traitement en while n'est pas effectué). Soit gauche <= droite.

Si tableau [centre] == cible, J'essaye de renvoyer la valeur de centre et de sortir du traitement dans la méthode avec le retour.

Ligne 20 elements_num = array.count --1 obtient l'indice le plus à droite du tableau. Peut-être que la longueur est bonne au lieu de compter.

S'il s'agit d'un tableau non trié

Vous pouvez trier par ʻarray name.sort`.

fin

Il existe un moyen de comparer en utilisant chaque méthode, mais plus le tableau contient de contenu, plus la recherche binaire est pratique. En passant, je me demande si une certaine application qui était populaire auprès d'amis dans le passé utilisait ce mécanisme.

Ça fait longtemps. Merci de rester avec nous jusqu'à la fin.

Recommended Posts

Utilisez la recherche binaire pour voir s'il y a des valeurs dans le tableau
Si vous utilisez SQLite avec VSCode, utilisez l'extension (comment voir le fichier binaire de sqlite3)
Comment créer une partie d'espace réservé à utiliser dans la clause IN
Comment ajouter les mêmes index dans un tableau imbriqué
J'étais confus parce qu'il y avait une scission dans le tableau
[Java] Comment rechercher des valeurs dans un tableau (ou une liste) avec la méthode contains
Juger si les chaînes de caractères à comparer sont les mêmes en Java
Que faire si les modifications ne sont pas reflétées dans le fichier manifeste JAR
Volume qui souhaite utiliser de nombreux opérateurs logiques dans l'instruction if
Comment faire une méthode de jugement pour rechercher n'importe quel caractère dans le tableau
Implémentez l'algorithme dans Ruby: Day 3-Dichotomy-
Méthode de recherche arbitraire dans un tableau utilisant la recherche binaire
Même si je souhaite convertir le contenu d'un objet de données en JSON en Java, il existe une référence circulaire ...
[Maven] Que faire si on vous demande d’incorporer dans la guerre un fichier jar qui n’est pas dans le référentiel distant
La bonne façon de voir la source Tomcat dans Eclipse
Une brève introduction à terasoluna5, voir le texte ci-dessous
Comment utiliser un tableau pour la clé TreeMap
Je veux intégrer n'importe quel TraceId dans le journal
Je veux utiliser une petite icône dans Rails
Calculer la différence entre les nombres dans un tableau Ruby
Comment convertir un fichier en tableau d'octets en Java
Mémo qui passe à l'écran de connexion si vous n'êtes pas connecté avec l'appareil