Binäre Suche: Unterschied zwischen den Versionen

Aktuelle Version vom 6. Dezember 2016, 13:59 Uhr

Iterative Suche Bei der binären Suche wird nach einem Objekt in einem Array mit folgendem Algorythmen gesucht: Zuerst wird die Mitteberechnet indem die linke Schranke mit dem Quotienten aus der Differenz der rechten und linken Schranke und zwei (mitte = links + (rechts - links)/2). Dann wird geguckt ob die errechnete Mitte das gesuchte Objekt ist. Ist sie es, so ist die Suche beendet, ist sie es nicht so wird geguckt ob das Objekt größer sein muss als die errechnete Mitte. Ist der Wert größer so gilt: links = mitte +1. Ist der Wert kleiner so gilt : rechts = miite -1. Dieser Vorgang wird so lange wiederholt bis das entsprechende Objekt gefunden wurde. Falls die linke Schranke Rechts von der rechten ist (oder umgekehrt), so wird angegeben, dass das gesuchte Objekt nicht existiert.

Rekursive Suche Die rekursive Suche funktioniert fast gleich, nur dass die Mitte aus dem Quotienten der Summe aus links und rechts und zwei berechnet wird ((links + rechts)/2).[

Datei:BinäreSucheBild

Beispiele Iterative Suche Wir haben einen Stapel von 11 CDs, welche Alphabetisch sortiert sind, und suchen die Beatles.

0 1 2 3 4 5 6 7 8 9 10 CD1 CD2 CD3 CD4 CD5 CD6 CD7 CD8 CD9 CD10 CD11

Also errechnen wir die Mitte mit dem Algorythmus : 0+(10-0)/2=5. Darauf decken wir die 5 auf. 0 1 2 3 4 5 6 7 8 9 10 CD1 CD2 CD3 CD4 CD5 Micheal Jackson CD7 CD8 CD9 CD10 CD11