[RUBY] Beliebige Suchmethode in einem Array mit binärer Suche

【Überblick】

1. Schlussfolgerung </ b>

2. Was ist eine binäre Suche? </ B>

3. So codieren Sie </ b>

4. Was ich hier gelernt habe (im Fehlerfall verwendet) </ b>

  1. Fazit

Verwenden Sie die Methode length in Kombination mit der while-Anweisung und der if-Anweisung </ b>!
2. Was ist binäre Suche?

Dies ist eine Suchmethode für Daten in einem Array (vorausgesetzt, dass nicht derselbe Wert enthalten ist). Der Inhalt ist eine Suchmethode, die den Wert in der Mitte überprüft, die Größenbeziehung zwischen links und rechts vergleicht und nacheinander sucht!
3. Wie man codiert

def binary_search(array, number_factors, value)
  min_factor = 0
  max_factor = number_factors - 1 #---❷
  while min_factor <= max_factor do #---❸
    center_factor = (min_factor + max_factor) / 2 #---❹
    if array[center_factor] == value
      return center_factor
    elsif array[center_factor] < value
      min_factor = center_factor + 1
    else
      max_factor = center_factor - 1 #---❺
    end
  end
  return -1 #---❻
end

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

puts "Welche Nummer suchen Sie?"
value = gets.to_i
number_factors = array.length #---❶

result = binary_search(array, number_factors, value)

if result == -1 #---❼
  puts "#{value}Ist derzeit nicht registriert."
else
  puts "#{value}Ist#{result}Es ist der zweite."
end

❶: Zählen Sie zuerst die Elemente des Arrays im Array. Die binäre Suche beginnt mit der Aufteilung des Elements in zwei Hälften.
❷: Die Nummer des Elements ganz links und die Nummer des Elements ganz rechts werden festgelegt. Da "0" ganz am Anfang des Arrays angewendet wird, ist das linke Ende 0 und das rechte Ende die Anzahl der Elemente einschließlich 0, daher wird "-1" verwendet. (Es gibt 10 Elemente bis zum Beispiel: 1 ... 31, aber das Element beginnt mit "0" am linken Ende, sodass es am rechten Ende zu "9" wird.)
❸: Hier werden die Anzahl der Elemente von links und die Anzahl der Elemente von rechts verglichen. Dies liegt daran, dass die Zahl ganz links die Zahl ganz rechts nicht überschreitet.
❹: ❹ bis ❻ sind die Hauptteile der binären Suche. Ich habe das zentrale Element mit center_factor gefunden. Wenn die Elemente des Arrays ungerade sind, werden sie automatisch gerundet.





Recommended Posts