Implementieren Sie den Algorithmus in Ruby: Tag 3-Dichotomie-

Es macht Spaß, Ruby kürzlich zu schreiben. 3. Tag. Klicken Sie hier für den zweiten Tag <Implementierung des Algorithmus in Ruby: Tag 2 - Blasensortierung>

Was ist eine Zweiteilung?

Ein Algorithmus, der schnell bestimmte Daten findet, indem er den Vorgang des Eingrenzen der sortierten Daten in zwei Hälften wiederholt. Sehr berühmt und leicht vorstellbar. Also lasst uns codieren

binarySearch.rb

#Halbierungssuche
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 "Nummer zum Speichern:"
num = gets.split().map(&:to_i)
print "Zu suchende Nummer:"
tar = gets.to_i
binary = binarySearch(num, tar)

if binary >= 0
  puts "#{binary+1}Zweitens gefunden."
else
  puts "Es gibt keine Zahlen"
end

Ausgabe

Nummer zum Speichern:1 2 3 4 5 6 7 8 9
Zu suchende Nummer: 6
Gefunden 6 ..

Codekommentar

binarySearch Definiert eine Methode zum Durchführen einer binären Suche Argumente sind Daten und der Wert, den Sie suchen möchten Ersetzen Sie den Anfang und das Ende der Sequenz durch Start bzw. Länge Ersetzen Sie die Hälfte durch eine Zahl, die den Wert in der Mitte des Arrays angibt Ersetzen Sie mid durch den Wert der Datenmitte Wiederholen Sie diesen Vorgang, bis der Wert in der Mitte und der Wert, den Sie überprüfen möchten, identisch sind.

Wenn die Hälfte kleiner als 0 oder größer als die Anzahl der Daten ist, wird die Hälfte als -1 zurückgegeben. Kurz gesagt, es gab keine Daten. Behandeln Sie sie daher als falsch.

Wenn die Daten in der Mitte und der Wert, den Sie überprüfen möchten, identisch sind, endet die Schleife

Wenn die Daten in der Mitte größer sind als der Wert, den Sie überprüfen möchten, verschieben Sie das Ende

Wenn die Daten in der Mitte kleiner als der Wert sind, den Sie untersuchen möchten, verschieben Sie den Ansichtspunkt

Geben Sie die Werte für halb und mittel erneut ein

Gibt die Hälfte zurück, wenn die Schleifenverarbeitung abgeschlossen ist.

Geben Sie Daten ein und geben Sie die Nummer aus.

Schließlich

Das Bild der Exploration kam schnell, aber die Umsetzung dauerte länger als erwartet. Oft schlug die Suche fehl, weil sich Start und Ende nicht gut bewegten.

Da es sich bei der Dichotomie um eine sortierte Datensuche handelt, ist es möglicherweise besser, sie mit der zuletzt implementierten Blasensortierung zu kombinieren.

Ich denke nicht, dass der Code selbst korrekt ist, aber es fühlt sich wie viel Verschwendung an. Ich meine, es gibt einen besseren Weg

Nun, das nächste Mal werde ich eine lineare Suche implementieren (ich habe auf jeden Fall einen Fehler in der Reihenfolge gemacht)