Binäre Suche – Die Idee
Die Binäre Suche verdankt ihren Namen der Überlegung, dass bei einem sortierten assoziativen Array (Key,Value) die Anzahl der benötigten Schlüsselvergleiche halbiert werden kann. Man nimmt den gegebenen Suchschlüssel und vergleicht dessen Wert mit dem Wert des mittleren Arrayelements. Wenn man Glück hat kann die Suche hier schon beendet sein. Wenn nicht wiederholt sich der Vorgang, entweder für die linke oder die rechte Hälfte des Arrays. Welches der beiden Segmente gewählt wird hängt davon ab, ob der gefundene Schlüsselwert größer oder kleiner als der Suchschlüssel war. Diesen Schritt wiederholt man solange, bis entweder das gesuchte Element gefunden wurde oder keine weitere Aufteilung mehr möglich ist. In diesem Fall konnte das gesuchte Element nicht gefunden werden.
Einfaches binäres Suchbeispiel
Beispielablauf einer binaeren Suche
Quelle: Algorithmen und Datenstrukturen
Pomberger,Dobler
Implementierungsbeispiel Java – interativ
/**
* @param A Array mit den Elementen
* @param searchKey gesuchter Schlüssel
* @param lr Linker Rand
* @param rr Rechter Rand
* @return Index des gefundenen Schlüssel, ansonsten -1
*/
public static int binaereSuche(int[] A, int searchKey, int lr, int rr){
while(lr<=rr){
int mitte = (lr + rr)/ 2;
if (A[mitte] == searchKey) return mitte;
if (A[mitte] > searchKey) rr= mitte-1;
if (A[mitte] < searchKey) lr= mitte+1 ;
}
return -1;
}
Implementierungsbeispiel Java – rekursiv
/**
* @param A Array mit den Elementen
* @param searchKey gesuchter Schlüssel
* @param lr Linker Rand
* @param rr Rechter Rand
* @return Index des gefundenen Schlüssel, ansonsten -1
*/
public static int binaereSucheRekursiv(int[] A, int searchKey, int lr, int rr){
if(lr > rr) return -1;
int mitte = (lr + rr) / 2;
if (A[mitte] == searchKey)
return mitte;
if (A[mitte] > searchKey)
return binaereSucheRekursiv(A, searchKey, lr, mitte-1);
if (A[mitte] < searchKey)
return binaereSucheRekursiv(A, searchKey, mitte+1, rr);
return -1;
}
Erfahrungen mit der Komplexität
Um in einem Array mit i Einträgen ein Element zu durchlaufen werden maximal [log2 n] Schritte benötigt. Somit liegt die Komplexität innerhalb der Klasse O(log n) was prinzipiel ein erstrebenswertes Laufzeitverhalten ist.
- Implementierung der binären Suche in Java und C: http://de.wikipedia.org/wiki/Binäre_Suche
- Binäre Suche im Java SDK: http://java.sun.com/javase/
- Siehe auch: http://hurm-it.de/blog/non-web-coding/quicksort/
Als kleines Beispiel verwende ich diesen Blog. Um Strukturen abzubilden, bieten sich besonders die bereits bestehenden inhaltlichen Kategorien bzw. Gruppierungen an. Sie vermitteln zunächst einen groben Umriss des Inhalts. Bei entsprechend großen Seiten werden die entstehenden Listen schnell lang, womit eine adequate Gliederung sehr wichtig wird. Ziel sollte dabei sein, die vorhandenen Informationen möglichst leicht verständlich darzustellen, damit jeder Besucher sofort die Seite überblicken kann.