Inhaltsverzeichnis:
Definition - Was bedeutet binäre Suche?
Ein binärer Suchalgorithmus wird verwendet, um die Position eines bestimmten Werts in einem sortierten Array zu finden. Dieser Suchalgorithmus arbeitet nach dem Prinzip der Teilung und Eroberung und kann recht schnell sein. Der Nachteil ist jedoch, dass die Daten in sortierter Form vorliegen müssen. Es funktioniert, indem die Suche in der Mitte des Arrays gestartet 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 gehen muss, wenn nicht, muss der absteigende Teil des Arrays überprüft werden.
Eine binäre Suche wird auch als Halbintervallsuche oder logarithmische Suche bezeichnet.
Techopedia erklärt die binäre Suche
Eine binäre Suche ist eine schnelle und effiziente Methode, um einen bestimmten Zielwert aus einer Reihe von bestellten Artikeln zu ermitteln. Indem 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 absteigend sein soll.
Beispiel: Mit einem Zielwert von 8 und einem Suchbereich von 1 bis 11:
- Der Median / mittlere Wert gefunden wird, und der Zeiger wird gesetzt, was in diesem Fall 6 ist.
- Das Ziel von 8 ist im Vergleich zu 6 6. Da die kleiner als 8 ist, muss das Ziel in der höheren Hälfte sein.
- 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.
- 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 die Suche vom ersten Wert an begonnen und sich nach oben bewegt, wobei das Ziel mit acht Werten verglichen werden musste. Eine binäre Suche ist nur mit einem geordneten Datensatz möglich; Wenn die Daten zufällig angeordnet sind, liefert eine lineare Suche die ganze Zeit über Ergebnisse, während eine binäre Suche wahrscheinlich in einer Endlosschleife stecken bleibt.
