Binäre Suche

Definition - Was bedeutet binäre Suche?

Ein binärer Suchalgorithmus wird verwendet, um die Position eines bestimmten Werts zu finden, der in einem sortierten Array enthalten ist. Nach dem Prinzip des Teilens und Eroberens kann dieser Suchalgorithmus recht schnell sein, aber die Einschränkung besteht darin, dass die Daten in sortierter Form vorliegen müssen. Es funktioniert, indem die Suche in der Mitte des Arrays gestartet wird und die erste untere oder obere Hälfte der Sequenz durchlaufen wird. Wenn der Medianwert niedriger als der Zielwert ist, bedeutet dies, dass die Suche höher sein muss. Wenn nicht, muss der absteigende Teil des Arrays überprüft werden.

Eine binäre Suche wird auch als Halbintervallsuche oder logarithmische Suche bezeichnet.

Technische.me erklärt die binäre Suche

Eine binäre Suche ist eine schnelle und effiziente Methode, um einen bestimmten Zielwert aus einer Reihe geordneter Artikel zu finden. Wenn Sie in der Mitte der sortierten Liste beginnen, können Sie den Suchraum effektiv halbieren, indem Sie anhand des Medianwerts im Vergleich zum Zielwert festlegen, ob die Liste auf- oder absteigen soll.

Zum Beispiel mit einem Zielwert von 8 und einem Suchraum von 1 bis 11:

  1. Der Median / Mittelwert wird gefunden und der Zeiger wird dort gesetzt, in diesem Fall 6.
  2. Das Ziel von 8 wird mit 6 verglichen. Da 6 kleiner als 8 ist, muss sich das Ziel in der höheren Hälfte befinden.
  3. Der Zeiger wird zum nächsten Wert (7) bewegt und mit dem Ziel verglichen. Es ist kleiner, daher bewegt sich der Zeiger zum nächsthöheren Wert.
  4. Der Zeiger ist jetzt auf 8. Wenn man dies mit dem Ziel vergleicht, ist es eine exakte Übereinstimmung, daher wurde das Ziel gefunden.

Bei der binären Suche musste das Ziel nur mit drei Werten verglichen werden. Im Vergleich zu einer linearen Suche hätte sie vom ersten Wert an begonnen und wäre nach oben gegangen, wobei das Ziel mit acht Werten verglichen werden müsste. Eine binäre Suche ist nur mit einem geordneten Datensatz möglich. Wenn die Daten zufällig angeordnet sind, würde eine lineare Suche die ganze Zeit über Ergebnisse liefern, während eine binäre Suche wahrscheinlich in einer Endlosschleife stecken bleibt.