Binäre Suche - godx.de

Die binäre Suche hilft sehr schnell zu entscheiden, ob ein Element in einem sortierten Datenfeld vorhanden ist. Dabei werden maximal nur log2(n) Vergleiche benötigt, die Position zu finden, an der dieses Element sein sollte sofern vorhanden.

Beispiel (Quellcode): binarysearch.cpp
Download (Quellcode): binarysearch.zip

Beschreibung

Die binäre Suche schaut in der Mitte des Datenfeldes, ob der gesuchte Wert größer oder kleiner des Feldschlüsselwertes ist. Ist er kleiner, wird der untere Teil des Datenfeldes weiter benutzt, im anderen Fall der obere. Bei nächsten Durchlauf, wird mit dem entsprechenden Teilfeld weitergearbeitet. Die Suche ist beendet, wenn nur noch ein Element vorhanden ist und dieses dem gesuchten Wert entspricht.

Aufgrund dieser Vorgehensweise, ist es unbedingt notwendig, dass dieses Datenfeld sortiert ist. Nur in diesem Fall kann davon ausgegangen werden, dass nach dem Wertevergleich, das entsprechende Teilfeld den Suchwert nicht enthalten kann.

Beispieldarstellung

In diesem Bild wird die Suche nach dem Wert 18 veranschaulicht. Über 13 verschiedene Werte wird gesucht, dabei werden vier Schritte/Vergleiche durchgeführt.

Binäre Suche Schaubild

Erweiterungen

Bei der binären Suche, wird oft bloß ein Schlüsselwert zugelassen, dies muss aber nicht unbedingt so sein. Je nach Anforderung können auch duplizierte Schlüsselwerte, zugelassen werden. Es unterliegt dann der Programmdefinition, ob zum Beispiel bei einem Löschen eines solchen, alle gleichen Schlüsselwerte gelöscht werden oder nur der Erste usw. usf.

Auch die binäre Suche kann zum Sortieren verwendet werden (Einfügesortierung/Insertionsort), jedoch gibt es hier schnell Nachteile auf Grund des großen Zeitaufwandes durch das Elementkopieren im Datenfeld, um Platz für das neue Element zu schaffen.

Designüberlegungen

Desweiteren sollte im während des Designs der Programmabläufe, schon ermittelt werden, ob es sich lohnt die binäre Suche zu benutzen. Bei stark variierenden Datenfeldern, kann eine Sortierung mit anschließender Suche langsamer sein, als das ganze Datenfeld Element für Element zu vergleichen.

Durch den Beispielcode

Der Beispielcode, enthält eine Templateklasse (C++), die wesentliche Methoden besitzt:

die Suchfunktion
```
size_t FindKey(const _TYPE& key)
```
```
64
```
Gibt die erste Position des Elements zurück, dass mit dem Suchwert übereinstimmt, andernfalls size() des Datenfeldes.
die Einfügefunktion
```
size_t InsertKey(const _TYPE& key)
```
```
46
```
Gibt die Position des neuen Elements zurück. Gleiche Schlüssel lassen sich einfügen.
die Löschfunktion
```
void RemoveKey(const _TYPE& key)
```
```
53
```
Löscht alle Elemente mit dem Schlüsselwert.
die Näherungsfunktion
```
size_t NearestKey(const _TYPE& key, bool bMatch)
```
```
19
```
Bei bMatch auf false, wird die Position des Elements zurückgegeben, welches dem Suchwert am ähnlichsten aber größer ist. bMatch auf true entspricht einem FindKey und sucht nach dem exakten Wert.
die Vergleichsfunktion
```
int Compare(const _TYPE& left, const _TYPE& right)
```
```
74
```
Zwei Elemente werden miteinander verglichen. Dies wird durch die Suchfunktion aufgerufen und muss für den jeweiligen Objekttyp spezialisiert werden.

Rückgabewerte:
- < 0 = Element ist "kleiner"
- = 0 = Element ist gleich
- > 0 = Element ist "größer"

Codeanmerkungen

Die Ausrufparameter des Programms, bis auf das letzte, werden als sortierende Elemente benutzt:

CBinarySearch_String search;
for(int n=1; n<argc-1; n++)
    search.InsertKey(argv[n]);

99
100
101

Der letzte Aufrufparameter wird in der Liste gesucht und gelöscht.

size_t nPosition = search.FindKey(argv[argc-1]);
...
search.RemoveKey(argv[argc-1]);

110
111
112

So ergibt

./binarysearch binary array search array

die Ausgabe

Binary search test...

std::string:
   sorted 3 elements:
      1. array
      2. binary
      3. search

   element found at position 1

   result 2 elements:
      1. binary
      2. search