• Artikel
• Bearbeiten
• Historie
• Druckansicht

Binäre Suche

Die binäre Suche liefert in einem Array recht schnell das gesuchte Element bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes. Voraussetzung ist, dass die Elemente des Array in einer dem Suchbegriff entsprechenden Weise vorsortiert sind. Der Algorithmus basiert auf dem Schema Teile und Herrsche?.

Algorithmus

Zuerst wird das mittlere Element des Arrays überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche (vorzeitig) beendet.

Jede weiterhin zu untersuchende Hälfte wird wieder gleich behandelt: Das mittlere Element liefert wieder die Entscheidung darüber, wo bzw. ob weitergesucht werden muss.

Die Länge des Suchbereiches wird von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf 1 Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor.

Der Algorithmus zur binären Suche wird entweder iterativ oder als Rekursion implementiert.

Beispiel