|
Anwendung: sortierte Arrays und sortierte Dateien mit Direktzugriff
Auch bei der binären Suche werden die Datensätze in einem Array gespeichert, allerdings sortiert. Um festzustellen ob ein Schlüssel in dem Array vorhanden ist, wird zuerst das Element auf der mittleren Position mit ihm verglichen. Wenn der Schlüssel größer ist, muß sich das gesuchte Element in der ersten Hälfte des Arrays befinden, wenn er kleiner ist in der zweiten Hälfte und wenn er gleich ist, hat man das gesuchte Element gefunden. Ist das Element nicht das mittlere, dann wird das Array geteilt, und der ganze Vorgang wiederholt, bis man das Element gefunden hat.
Um das mittlere Element zu finden, bedient man sich folgender Formel: x = (l + r) / 2
l ... kleinster Index im Intervall des Arrays
r ... größter Index im Intervall des Arrays
Beispiel:
Inhalt des Arrays: A A A C E E E G H I L M N P R S X
Gesuchtes Element: M
A A A C E E E G H I L M N P R S X l: 1 r:17 x: 9
I L M N P R S X l:10 r:17 x:14(,5)
I L M l:10 r:12 x:11
M l:12 r:12 x:12
Die binäre Suche erfordert für eine erfolgreiche als auch für eine erfolglose Suche niemals mehr als
ld (n + 1) Vergleiche.
Algorithmus:
int binsearch (int v) // v ... Suchschlüssel
{ // Voraussetzung: Schlüssel >= 0
int l = 1, r = n, x;
while (r >= 1) {
x = (l + r) / 2;
if (v < a[x].key) r = x - 1;
else l = x + 1;
if (v == a[x].key) return a[x].info;
}
return -1;
}
Eine mögliche Verbesserung bei der binären Suche besteht in dem Versuch, genauer zu erraten, wo sich der gesuchte Schlüssel innerhalb des aktuell interessanten Intervalls befinden könnte (anstatt bei jedem Schritt blindlings das mittlere Element zu verwenden). Dies erinnert an die Art und Weise, wie man eine Nummer aus einem Telefonverzeichnis sucht: Falls der gesuchte Name mit B beginnt, schlägt man weiter vorne nach, falls er dagegen mit Y beginnt, such man näher beim Ende. Diese Methode nennt sich Interpolationssuche. Dabei müssen die Schlüssel auf Zahlenwerte abgebildet werden...
Vorteil: Schneller als sequentielle Suche
Nachteil: Nur geeignet bei statistischen Datensätzen, d.h. es wird selten etwas hinzugefügt oder gelöscht.
|
