[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. 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. 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. 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.