Schreiben wir Code, um herauszufinden, ob im Array ein Wert vorhanden ist. Wenn im Array kein Wert vorhanden ist, wird "Wert im Array nicht vorhanden" angezeigt Wenn vorhanden, zeigen Sie die Nummer im Array an.
Array = [1,3,5,6,9,10,13,20,26,31]
Die Suche erfolgt über eine binäre Suche (zweiteilige Suche).
Wenn Sie nach Daten in einer sortierten Liste oder einem sortierten Array suchen (vorausgesetzt, es gibt keine identischen Werte), überprüfen Sie den Mittelwert und verwenden Sie die Größenbeziehung mit dem Wert, nach dem Sie suchen möchten. Der Wert, nach dem Sie suchen möchten, befindet sich in der Mitte. Eine Methode zum Suchen, während überprüft wird, ob der Wert rechts oder links ist, und um sicherzustellen, dass er auf einer Seite nicht vorhanden ist. Da die Auswahl in einem Prozess halbiert wird, kann eine Verbesserung der Verarbeitungsgeschwindigkeit erwartet werden.
Bitte geben Sie die Nummer ein, nach der Sie suchen möchten
5
5 ist der zweite im Array
Bitte geben Sie die Nummer ein, nach der Sie suchen möchten
7
7 existiert nicht im Array
Verwenden Sie zunächst die .count-Methode, um die Werte im Array abzurufen, und verwenden Sie die Variable number_of_elements. Halbieren wir die Anzahl der Elemente im Array in der Methode binary_search als Variablenzentrum. Verwenden Sie die while-Anweisung, um die Berechnung zu wiederholen, bis sie gilt.
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 "Bitte geben Sie die Nummer ein, nach der Sie suchen möchten"
target = gets.to_i
number_of_elements = array.count
result = binary_search(array, number_of_elements, target)
if result == -1
puts "#{target}Existiert nicht im Array"
else
puts "#{target}Ist ein Array#{result}Existiert an zweiter Stelle"
end
Sehen Sie sich den Mittelwert in den Zeilen 1 bis 14 an und bestimmen Sie anhand der Größenbeziehung mit dem Wert, den Sie suchen möchten, ob der Wert, den Sie suchen möchten, rechts oder links vom Mittelwert liegt und auf einer Seite vorhanden ist. Wir führen eine Suche durch und stellen dabei sicher, dass dies nicht der Fall ist. Rückgabe -1 in Zeile 13 ist der endgültige Rückgabewert, wenn nichts zutrifft.
Betrachten Sie beispielsweise den Fall, in dem Sie 31 als Ziel eingeben. Dann läuft die Verarbeitung in der 2. bis 12. Zeile wie folgt ab.
#1. Schleife
left=0
right=10
center=5
array[center]=10
#Zweite Schleife
left=6
right=10
center=8
array[center]=26
#3. Schleife
left=9
right=10
center=9
array[center]=31
Dann gibt das Rückgabezentrum in der 6. Zeile einen Wert von 9 zurück, und die Verarbeitung in der 24. bis 28. Zeile gibt aus, dass 31 an der 9. Position im Array vorhanden ist.
(1) Definieren Sie zunächst die Nummer, die Sie als Ziel suchen möchten, die Nummer im Array als Anzahl der Elemente und das Ergebnis als Ergebnis. Die Nummer im Array kann mit der count-Methode array.count sein. Das Ergebnis wird durch result = binary_search (Array, Anzahl_der_Elemente, Ziel) dargestellt. Es scheint, dass Array ein Argument ist. (2) Schreiben Sie in die def-Methode. In der Beschreibung hierzu wird der Suchvorgang wie erläutert ausgeführt. Obwohl number_of_elements im Argument richtig ist, Da left = 0 ist, ist es verständlich, dass right number_of_elements ist. ③ Verwenden Sie wiederholt während Minuten. Da die "while" -Anweisung wiederholt ausgeführt wird, während der angegebene bedingte Ausdruck wahr ist, Diesmal wiederholen, bis left <= right wahr wird. ④ center = (links + rechts) / 2 steht für die Mitte. ⑤ if array[center] == target Wenn das Array [Medianwert] == die Nummer ist, nach der Sie suchen möchten. (6) Wenn dies in der while-Anweisung nicht der Fall ist, wird es von return-1 zurückgegeben. ⑦ Da das if-Ergebnis == -1 unten ist, wird angezeigt, dass es im Array nicht vorhanden ist. ⑧ Wenn es in der while-Anweisung in der Mitte wahr wird, verwenden Sie else im bedingten Ausdruck. Es wird angezeigt, dass # {target} an der # {result} -ten Position im Array vorhanden ist.
Recommended Posts