1	Binäre Suche Ein Suchverfahren in geordneten Feldern
2	Einordnung Schnelles Suchverfahren in geordneten Feldern Verwandte Verfahren Sequentielle Suche Interpolationssuche Fibonaccisuche Blocksuche
3	Voraussetzung Sortierter Array AR[0..n-1] mit lexikalischer Ordnung K (z.B. <, strcmp) AR[0] ≤ AR[1] ≤ … AR[i] … ≤ AR[n-1] Fragestellung: Ist Objekt (Zahl, Zeichenkette etc.) S in AR enthalten ? Beispiel:
4	Umgangssprachliche Formulierung Vergleiche das mittlere Element des Arrays (Pivotelement) mit dem Suchelement. Wenn gleich, dann ist das Suchelement gefunden wenn Pivotelement kleiner als das Suchelement, dann suche in der linken Arrayhälfte weiter wenn Pivotelement größer als das Suchelement, suche in der rechten Arrayhälfte weiter
5	Algorithmus Array[n/2]< S => weiter rekursiv mit Array[n/2..n] Array[n/2]> S => weiter rekursiv mit Array[1..n/2] Array[n/2]== S ist S gefunden Array[n/2] == {} S nicht vorhanden
6	Iterativer Algorithmus in Perl
7	Rekursiver Algorithmus in Perl
8	Beispiel 1
9	Beispiel 2
10	Anmerkungen zum Algorithmus Algorithmenklassifikation Divide and Conquer Strategie ("Teile und herrsche") Divide: Zerlege Problem in zwei gleich große Teilprobleme Conquer: Löse Teilproblem auf dieselbe Art
11	Terminiert der Algorithmus immer ? Ja, da bei jedem Schleifendurchlauf oder Rekursionsaufruf das Suchintervall halbiert wird. Voraussetzung ist natürlich, dass der Algorithmus richtig umgesetzt wird !
12	Anzahl der notwendigen Vergleiche Der Algorithmus benötigt Minimal 1 Suchelement = Mittelelement Maximal log₂n Suchelement ist Blatt Durchschnittlich log₂n – 1 Hälfte der Knoten im Suchzweig Vergleiche. Anmerkung: log₂n = log n / log 2
13	Maximale Vergleiche N Jeder Schleifendurchlauf halbiert das Intervall der Länge K. Beendet, wenn Intervalllänge = 1 K₁=K, K₂=K₁/2, K₃=K₂/2=K₁/2/2=K₁/4 … K = 2^N-1 N = log₂K
14	Binäre Suche als binärer Baum
15	Nochmals Vergleiche … Balanzierter binärer Baum der Höhe n Knotenanzahl K = = 2ⁿ-1 n = log₂K Ø = Ø(K/2) = Ø ( ) = log₂K - 1
16	Wann binäre Suche ? Falls nicht sortierter Array vorliegt, müssen die Kosten des Sortierens mitberücksichtigt werden Programmiersprachen C - bsearch Funktion Java – binarySearch (Arrays, Collections) Einfach zu implementieren für Arrays Zusätzliche andere auf der lexikalischen Ordnung basierende Vergleichsfunktionen notwendig Sortierte Stichwortliste in Wörterbüchern
17	Verbesserungsmöglichkeiten Bei bekannten Intervallen nur innerhalb des passenden Intervalls suchen Bei Alphabet innerhalb A, B … Z getrennt Erweiterung der Suchfunktion
18	Algorithmus …
19	Verallgemeinerter Suchalgorithmus
20	Verwandte Suchverfahren Interpolationssuche Zuerst grobe Abschätzung, wo sich der gesuchte Wert befinden könnte – Telefonbuch; gleichverteilte Werte Fibonaccisuche Suchbereich nach Fibonacci-Folge aufgeteilt
21	Vergleich mit anderen Such-Algorithmen