Binäre Suche
Die binäre Suche kann man nur auf ein sortiertes Feld anwenden. Sie
arbeitet folgendermaßen:
Es wird der Schlüssel des Elements in der Mitte des Feldes mit
dem Suchschlüssel verglichen.
Wenn beide gleich sind, ist die Suche erfolgreich beendet. Ist der
Suchschlüssel kleiner, wird der Teil links vom gewählten Element
nach dem gleichen System untersucht. Ist der Suchschlüssel größer,
wird der Teil rechts vom gewählten Element nach dem gleichen System
uintersucht. Dies wird solange (maximal lg N + 1 mal) durchgeführt,
bis entweder das gesuchte Element gefunden wurde oder bis man merkt, dass
der Schlüssel nicht im Feld enthalten ist. Das letztere stellt man
fest, wenn sich der linke Feldbegrenzer weiter rechts befindet, als der
rechte Begrenzer (siehe Code).
Hier nun ein Beispiel für eine erfolgreiche Suche:
Man stelle sich ein Feld von hundert Elementen vor, mit den Schlüsseln
1 bis 100. Wir suchen nun nach der 32.
(Feld 1...100)
32 < 50
(Feld 1...49)
32 > 25
(Feld 26...49)
32 < 37
(Feld 26...36)
32 > 31
(Feld 32...36)
32 < 34
(Feld 32...33)
32 = 32
Obwohl die 32 an einer eher ungünstigen Position steht, sind 6
Vergleiche im Gegensatz zu 32 bei der sequentiellen Suche eine große
Steigerung an Effizienz. Diese Schnelligkeit macht sich besonders
bei sehr großen Feldern bemerkbar, bei denen die Anzahl der Vergleiche
bei der binären Suche kaum ansteigt.
dataType cm_BinaereSuche(itemType wert) {
int l = 1, r = N, teiler;
while(r >= l) {
teiler = (l+r)/2;
if(wert == feld[teiler].key)
return feld[teiler].daten;
if(wert < feld[teiler].key)
r = teiler - 1;
else
l = teiler + 1;
}
return keineDaten;
}
|
Computer
Programmieren (incl. C++ Kurs)
Algorithmen
Bücher
Zeitschriften
Heavy Metal
Mountainbiking
Meine Katze
Über mich und die Site
Links
Downloads
Gästebuch
HP mit Umfrage
