Implémentez l'algorithme dans Ruby: Day 3-Dichotomy-

C'est amusant d'écrire Ruby récemment. 3e jour. Cliquez ici pour le deuxième jour <Implémentation de l'algorithme dans Ruby: Day 2 -Bubble sort->

Qu'est-ce qu'une dichotomie?

Un algorithme qui trouve rapidement des données spécifiques en répétant l'opération consistant à réduire de moitié les données triées. Très célèbre et facile à imaginer. Alors codons

binarySearch.rb

#Recherche de bisection
def binarySearch(num, pat)
  start = 0
  len = num.length - 1
  half = (start + len) / 2
  mid = num[half]
  
  while mid != pat
    if half < 0 || half > num.length
      half = -1
      break
    elsif pat == mid
      break
    elsif pat < mid
      len = half - 1
    else
      start = half + 1
    end
    half = (start + len) / 2
    mid = num[half]
  end
  half
end

print "Numéro à stocker:"
num = gets.split().map(&:to_i)
print "Numéro à rechercher:"
tar = gets.to_i
binary = binarySearch(num, tar)

if binary >= 0
  puts "#{binary+1}Trouvé deuxième."
else
  puts "Il n'y a pas de chiffres"
end

production

Numéro à stocker:1 2 3 4 5 6 7 8 9
Nombre à rechercher: 6
Trouvé 6e.

Commentaire de code

binarySearch Définit une méthode pour effectuer une recherche binaire Les arguments sont des données et la valeur que vous souhaitez rechercher Remplacez respectivement le début et la fin de la séquence par start et len Remplacez la moitié par un nombre indiquant la valeur au milieu du tableau Remplacez la valeur du centre des données par mid Répétez jusqu'à ce que la valeur au centre et la valeur que vous souhaitez vérifier soient identiques.

Si la moitié est inférieure à 0 ou supérieure au nombre de données, la moitié est renvoyée sous la forme -1. En bref, il n'y avait pas de données, alors traitez-les comme fausses.

Si les données au centre et la valeur à vérifier sont les mêmes, la boucle se termine

Si les données au centre sont plus grandes que la valeur que vous souhaitez vérifier, décalez la fin

Si les données au centre sont plus petites que la valeur que vous souhaitez examiner, décalez le point de vue

Entrez à nouveau les valeurs pour moitié et milieu

Renvoie la moitié lorsque le traitement de la boucle est terminé.

Entrez les données et indiquez le nombre.

finalement

L'image de l'exploration est venue rapidement, mais sa mise en œuvre a pris plus de temps que prévu. Souvent, la recherche a échoué parce que le début et la fin ne se sont pas bien déroulés.

Étant donné que la dichotomie est une recherche de données triées, il peut être préférable de la combiner avec le tri à bulles implémenté la dernière fois.

Je ne pense pas que le code lui-même soit correct, mais cela ressemble à beaucoup de gaspillage. Je veux dire, il y a un meilleur moyen

Eh bien, la prochaine fois, je vais implémenter une recherche linéaire (j'ai fait une erreur dans l'ordre par tous les moyens)