Sie nutzen bisher noch keine binäre Suche für Ihr Embedded-Projekt? Ich verrate Ihnen, warum dieser Algorithmus so mächtig ist und die Effizienz Ihrer Firmware erheblich steigern kann.
Was ist Binary Search?
Die binäre Suche (Binary Search) ist ein hocheffizienter Algorithmus, der einen bestimmten Wert innerhalb eines sortierten Arrays findet. Sein Prinzip basiert darauf, das Array immer wieder in zwei Hälften zu teilen und nur in dem relevanten Intervall weiterzusuchen.
Wofür benötige ich die binäre Suche?
Immer wenn Sie große, sortierte Datenmengen durchsuchen müssen, ist dieser Algorithmus Ihr Helfer in der Not. Er reduziert die Anzahl der notwendigen Vergleiche dramatisch im Vergleich zu einer linearen Suche (bei der jedes Element einzeln geprüft wird).
Ein Beispiel aus der Praxis
Stellen Sie sich vor, Ihr Embedded-Steuergerät verwaltet eine große Menge an Datenpunkten, zum Beispiel von Sensoren. Um diese Daten schnell im CAN-Netzwerk zu verteilen, ist es üblich, jedem Datenpunkt eine eindeutige ID zuzuweisen. Sie haben also eine lange, sortierte Liste von IDs, die jeweils für einen bestimmten Messwert stehen.
Kommt nun eine Anfrage für den Datenpunkt mit der ID `100` herein, müssen Sie die zugehörigen Daten schnell finden. Hier glänzt die binäre Suche.
Die Funktionsweise im Detail
Der Algorithmus benötigt neben dem zu suchenden Wert (in unserem Beispiel `x = 100`) einen Pointer auf das Array sowie einen Start- (`low`) und Endindex (`high`). In jedem Schritt wird der mittlere Wert (`mid`) des aktuellen Intervalls berechnet und mit `x` verglichen:
- Ist der mittlere Wert gleich `x`, wurde das Element gefunden.
- Ist der mittlere Wert kleiner als `x`, wird die Suche im rechten (oberen) Intervall fortgesetzt.
- Ist der mittlere Wert größer als `x`, wird die Suche im linken (unteren) Intervall fortgesetzt.
Dieser Vorgang wird rekursiv wiederholt, wobei sich die Intervallgrenzen bei jedem Schritt anpassen. So werden in kürzester Zeit riesige Suchräume ausgeschlossen.
Die beeindruckende Performance
Die Stärke des Algorithmus wird bei großen Datenmengen deutlich. Während eine lineare Suche im schlimmsten Fall alle Elemente prüfen muss, reduziert die binäre Suche die Anzahl der Versuche logarithmisch. Für ein Array mit 1.000 Elementen benötigt die binäre Suche beispielsweise maximal 10 Versuche. Für eine Million Elemente sind es nur etwa 20. Fantastisch!
Zurück zur Übersicht