Teile und Herrsche 2 SS09
Inhaltsverzeichnis |
Diese Seite stellt eine inhaltliche Fortsetzung des Themas Teile und Herrsche 1 dar.
Zusammenfassung
Binäre Suche
Wie funktionierts?
Der Trick besteht also darin, den Suchraum stets zu halbieren und festzustellen in welcher Hälfte unsere gesuchte Information wohl zu finden ist, diese Hälfte wird dann wieder halbiert und es wird wieder verlgichen und so weiter... . Um nun auf einen konkreten Algorithmus und dessen Effizienzanalyse hinzuarbeiten, reduzieren wir das Problem auf eine aufsteigend sortierte Liste mit Integerzahlen. Da der zusätzliche Aufwand für das bestimmen der längenlexikographischen Ordnung wie oben erwähnt die Analyse nur unnötig erschwert.
Also nun zu unserer Liste:
$$L= \{ e_{1}, e_{2}, ... , e_{n} \}$$Wie erwähnt, muss die Liste bereits zu begin geteilt werden, dies geschieht beim Element mit dem Index k, die Mitte der Liste ist also k = \frac{n}{2}. Wobei man ja davon ausgehen kann, das die Liste nicht zwangsläufig ungerad zahlig viele Elemente besitzt, sodass man ein Element in der Mitte ausmachen kann. Also müssen wir unser k folgendermassen korrigieren k = \lfloor\frac{n}{2}\rfloor somit nehmen wir bei der Division den ganzzahligen Wert, nach unten gerundet.
Nun haben wir eine linke Teilliste L_{l}=\{a_{1}, a_{2}, ... a_{k}\} und eine rechte Teilliste L_{r}=\{a_{k+1}, a_{k+2}, ... a_{n}\} .
\underbrace{a_{1}, a_{2}, ... a_{k}}_{Liste_{l}}, \underbrace{a_{k+1}, a_{k+2}, ... a_{n}}_{Liste_{r}}Jetzt wird unser Zielwert x mit dem ersten Element a_{k+1} der rechten Liste x < a_{k+1} verglichen, jenach Ergebniss wird mit L_{r} oder L_{l} weiter gearbeitet. Natürlich kann bereits zu Begin der Elementarfall eintreten das a_{k} = x ist. Aber leider hat man in der Praxis wohl selten soviel Glück.
Fassen wir das nocheinmal zusammen: BinSuch = \