[RUBY] problème de recherche de rubis

problème

Écrivons du code pour savoir si une valeur existe dans le tableau. Si aucune valeur n'existe dans le tableau, "La valeur n'existe pas dans le tableau" s'affiche et S'il existe, affichez le numéro dans le tableau.

Tableau = [1,3,5,6,9,10,13,20,26,31]

La recherche est effectuée à l'aide d'une recherche binaire (recherche en deux parties).

Qu'est-ce que la recherche binaire?

Lorsque vous recherchez des données dans une liste ou un tableau triés (en supposant qu'il n'y a pas de valeurs identiques), examinez la valeur centrale et utilisez la relation de grandeur avec la valeur que vous souhaitez rechercher, et la valeur que vous souhaitez rechercher est au centre. Une méthode de recherche en vérifiant si la valeur est à droite ou à gauche et 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.

Exemple de sortie

Veuillez saisir le numéro que vous souhaitez rechercher
5
5 est le deuxième du tableau

Veuillez saisir le numéro que vous souhaitez rechercher
7
7 n'existe pas dans le tableau

Conseils

Tout d'abord, utilisez la méthode .count pour obtenir les valeurs du tableau et utilisez la variable number_of_elements. Réduisons de moitié le nombre d'éléments dans le tableau dans la méthode binary_search comme centre de la variable. Utilisez l'instruction while pour répéter le calcul jusqu'à ce qu'il s'applique.

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
      left = center + 1
    else
      right = center - 1
    end
  end
  return -1 
end

array=[1,3,5,6,9,10,13,20,26,31]

puts "Veuillez saisir le numéro que vous souhaitez rechercher"
target = gets.to_i
number_of_elements = array.count

result = binary_search(array, number_of_elements, target)

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

Commentaire

Examinez la valeur centrale des lignes 1 à 14 et utilisez la relation d'amplitude avec la valeur que vous souhaitez rechercher pour déterminer si la valeur que vous souhaitez rechercher se trouve à droite ou à gauche de la valeur centrale et qu'elle existe d'un côté. Nous effectuons une recherche en nous assurant qu'elle n'est pas effectuée. Le retour -1 à la ligne 13 est la valeur de retour finale lorsque rien ne s'applique.

Par exemple, considérez le cas où vous entrez 31 comme cible. Ensuite, le traitement se déroule comme suit sur les 2e à 12e lignes.

#1ère boucle
left=0
right=10
center=5
array[center]=10

#Deuxième boucle
left=6
right=10
center=8
array[center]=26

#3e boucle
left=9
right=10
center=9
array[center]=31

Ensuite, le centre de retour sur la 6ème ligne renvoie une valeur de 9, et le traitement sur les 24ème à 28ème lignes sort que 31 existe à la 9ème position dans le tableau.

Votre propre considération

(1) Tout d'abord, définissez le nombre que vous souhaitez rechercher comme cible, le nombre dans le tableau comme number_of_elements et le résultat comme résultat. Le nombre dans le tableau peut être array.count en utilisant la méthode count. Le résultat est représenté par result = recherche_binaire (tableau, nombre_éléments, cible). Il semble que le tableau soit un argument. (2) Écrivez dans la méthode def. Dans la description de celui-ci, le processus de recherche est exécuté comme expliqué. Bien que number_of_elements soit juste dans l'argument, Puisque left = 0, il est compréhensible que right soit number_of_elements. ③ Utilisez plusieurs minutes répétées. Étant donné que l'instruction "while" est exécutée à plusieurs reprises alors que l'expression conditionnelle spécifiée est vraie, Cette fois, répétez jusqu'à ce que gauche <= droite devienne vrai. ④ center = (gauche + droite) / 2 représente le centre. ⑤ if array[center] == target Si le tableau [valeur médiane] == est le nombre que vous souhaitez rechercher. (6) Si ce n'est pas vrai dans l'instruction while, il est renvoyé par return-1. ⑦ Puisque le résultat if == -1 ci-dessous, il est affiché qu'il n'existe pas dans le tableau. ⑧ Dans l'instruction while, si elle devient vraie au milieu, utilisez else dans l'expression conditionnelle. Il est affiché que # {target} existe à la # {result} ième position dans le tableau.