[RUBY] Verwenden Sie die binäre Suche, um festzustellen, ob das Array Werte enthält

Es ist eine Geschichte, die viele Leute bereits geschrieben haben, Ich möchte mein Verständnis durch Schreiben vertiefen, also werde ich es schreiben.

Problem

Lösen wir das folgende Problem mithilfe der binären Suche.

Es gibt ein Array array = [1, 3, 5, 6, 9, 10, 13, 20, 26, 34], Schreiben Sie Code, um herauszufinden, ob in diesem Array ein Wert vorhanden ist. Wenn im Array kein Wert vorhanden ist, wird "Wert im Array nicht vorhanden" angezeigt Wenn vorhanden, wird die Nummer im Array angezeigt.

#Ausgabebeispiel 1
Bitte geben Sie die Nummer ein, nach der Sie suchen möchten
5
5 ist der zweite im Array

#Ausgabebeispiel 2
Bitte geben Sie die Nummer ein, nach der Sie suchen möchten
8
8 existiert nicht im Array

Was ist überhaupt binäre Suche?

Bei der Suche nach sortierten Listen oder Daten in Arrays (vorausgesetzt, sie haben nicht denselben Wert) Sehen Sie sich den Wert in der Mitte an und verwenden Sie die Größenbeziehung mit dem Wert, den Sie suchen möchten. Bestimmen Sie, ob der Wert, nach dem Sie suchen möchten, rechts oder links vom Mittelwert liegt. Eine Suchmethode, bei der sichergestellt wird, dass sie nicht auf einer Seite vorhanden ist. Da die Auswahl in einem Prozess halbiert wird, kann eine Verbesserung der Verarbeitungsgeschwindigkeit erwartet werden. Wird auch als zweiteilige Suche oder zweiteilige Suche bezeichnet.

Ich werde ungefähr schreiben, wie es ist

Der Wert, den Sie suchen möchten, ist "Ziel". Der Index ganz links ist "links". Der Index ganz rechts ist "richtig". Der Index in der Mitte ist "Mitte" zugeordnet.

Übrigens werden wir diesmal mit target = 5 suchen.

Die folgende Abbildung zeigt die Anordnung. Lass es uns tatsächlich versuchen.

Bei der ersten Suche left = 0 right = 9 Und der Index mit dem zentralen Wert ist center = (left + right) / 2, dh center = 4. (Tatsächlich ist 9 geteilt durch 2 4,5, aber im Fall von Ruby ist Ganzzahl / Ganzzahl = Ganzzahl (nach dem Dezimalpunkt abgerundet), also ist dies in Ordnung.) Nachdem Sie den Index mit dem zentralen Wert kennen, vergleichen Sie ihn mit dem Wert, den Sie suchen möchten. array[center] = 9 target = 5 Also Array [Mitte]> Ziel. Jetzt kennen Sie den Bereich, in dem Sie als Nächstes suchen müssen. Es sieht aus wie in der Abbildung unten. Gray ist nicht auf der Suche. Wie Sie in der Abbildung sehen können, ändert sich das Recht. Da wird es auf die linke Seite der Mitte geändert right = center - 1

Natürlich ändert sich auch das Zentrum. Die Methode des Findens ist die gleiche wie beim ersten Mal. center = (left + right) / 2 Die zweite Berechnung ist übrigens Mitte = 1.

Vergleichen Sie dann wie beim ersten Mal den Mittelwert mit dem Wert, den Sie suchen möchten. array[center] = 3 target = 5 Also Array [Mitte] <Ziel.

Und Sie können den nächsten Suchbereich sehen. Diesmal blieben Änderungen übrig. Weil es eins rechts von der Mitte sein wird left = center + 1 Das Zentrum ändert sich ebenfalls. Die Methode zum Auffinden ist dieselbe wie zuvor. center = (left + right) / 2 Das dritte Mal wird übrigens als center = 2 berechnet.

Vergleichen Sie dann den Mittelwert mit dem Wert, den Sie wie zuvor suchen möchten. array[center] = 5 target = 5 array [center] == target und die Suche endet.

Antwortbeispiel

Ich werde es umschreiben, während ich das organisiere, was ich ungefähr oben geschrieben habe.

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]  #16. Zeile

puts "Bitte geben Sie die Nummer ein, nach der Sie suchen möchten"  #18. Zeile
target = gets.to_i
elements_num = array.count - 1

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

if result == -1  #24. Zeile
  puts "#{target}Existiert nicht im Array"
else
  puts "#{target}Ist ein Array#{result}Existiert an zweiter Stelle"
end

Ergänzung

Es gibt eine Beschreibung der binären Suche in der Methode binary_search.

Stellen Sie ein, um die Verarbeitung mit while zu wiederholen. Die Bedingung für die Gültigkeit der Wiederholung ist, bis der Index ganz links (links) des Arrays mit dem Index ganz rechts (rechts) des Arrays identisch wird (wenn er überschritten wird, wird die Verarbeitung in while nicht ausgeführt). Lassen Sie links <= rechts.

Wenn array [center] == target, Ich versuche, den Wert von center zurückzugeben und die Verarbeitung in der Methode mit return zu verlassen.

Zeile 20 elements_num = array.count --1 ruft den Index ganz rechts des Arrays ab. Vielleicht ist die Länge in Ordnung, anstatt zu zählen.

Wenn es sich um ein unsortiertes Array handelt

Sie können nach array name.sort sortieren.

Ende

Es gibt eine Möglichkeit, mit jeder Methode zu vergleichen, aber je mehr Inhalt des Arrays vorhanden ist, desto bequemer ist die binäre Suche. Ich frage mich übrigens, ob eine bestimmte App, die in der Vergangenheit bei Freunden beliebt war, diesen Mechanismus verwendet hat.

Es ist lange her. Vielen Dank, dass Sie bis zum Ende bei uns bleiben.