Binäre Suche (Beispiel, Laufzeit & Umsetzung in Java)
MatheSpeck
https://www.youtube.com/watch?v=v6HawhawtQY

Transkript (automatisch erstellt)

0:00 morgen zusammen wir schauen uns heute an wie die binäre Suche funktioniert wir haben ein Feld von Werten und sollen überprüfen ob ein vorgegebener
0:07 Suchschlüssel bzw suchwert auftaucht oder nicht und im Gegensatz zur linearen Suche haben wir hier eine wichtige Voraussetzung die erfüllt sein muss das
0:16 Feld muss nämlich sortiert sein in der Regel aufsteigend und was ist jetzt die Grundidee man prüft den Wert in der Mitte des Feldes Vergleich den mit dem
0:26 Suchschlüssel wenn die beiden gleich sind dann haben wir einen Treffer sollte der Suchschlüssel größer sein als der Wert in der Mitte dann betrachtet man
0:34 nur noch das rechte Teilfeld weil wegen der Sortierung kann der Schlüssel nur dort auftauchen andersrum genauso sollte der Suchschlüssel kleiner sein als der
0:44 Wert in der Mitte dann betrachtet man nur noch das linke Teilfeld und das Ganze wiederholt man bis man einen Treffer hat bzw kein Teilfeld mehr und
0:55 dann weiß man dass der Wert nicht auftaucht und wie funktioniert das jetzt für dieses konkrete Beispiel wir haben als erstes unsere Hilfsvariable POS in
1:05 der wir die Position des Treffers speichern die setzen wir zunächst auf einen ungültigen Wert -1 weil die Indizes ja bei ull anfangen zu zählen
1:14 und dann haben wir noch zwei weitere hilfsvariablen links und rechts die uns den Teilbereich angeben mit dem wir gerade arbeiten da wir mit dem gesamten
1:23 Array Beginn stehen hier die Indizes vom ersten Element also 0 und vom letzten el Element 9 drin und als nächstes berechnen wir den Mittelwert davon 0 + 9
1:36 sind 9 ge 2 sind 4,5 wenn man ohne Rest rechnet also abrundet kommt 4 heraus man könnte auch aufrunden aber wenn man mit Integern arbeitet dann werden die
1:47 Nachkommastellen ohnehin abgeschnitten das heißt hier abzurunden ist die natürlichere Variante und an der Position 4 haben wir den Wert 50 den
1:57 vergleichen wir mit dem Suchschlüssel diesind nicht gleich das heißt wir gucken jetzt ist unser Suchschlüssel größer als 50 ja weil 67 ist größer und
2:07 das heißt wir wollen jetzt nur noch mit dem rechten Teilfeld weiterarbeiten wie machen wir das indem wir den linkszeiger auf das erste Element hinter den Wert in
2:18 der Mitte schieben das heißt auf die fünf und damit haben wir schon mal die Hälfte vom Feld eliminiert und das wiederholen wir jetzt
2:26 mit dem neuen Teilfeld das heißt wir berechnen den Mittelwert von 5 und 9 5 + 9 sind 14 ge 2 sind 7 das heißt wir vergleichen die 73 mit der 67 die sind
2:39 nicht gleich das heißt wir haben keinen Treffer und gucken jetzt ist die 67 größer oder kleiner als 73 sie ist kleiner das heißt wegen der Sortierung
2:48 muss falls überhaupt der Treffer im linken Teilfeld liegen das heißt wir setzen rechts auf den Wert links von der Mitte das heißt auf die 6 und erhalten
2:59 damit diese zwei Elemente als neues teilarray dann wiederholen wir den Vorgang wieder das heißt wir bilden die Mitte aus 5 und 6 5 + 6 sind 11 ge 2
3:10 sind 5,5 also abgerundet 5 das heißt jetzt zeigen Mitte und links auf das gleiche Element was völlig in Ordnung ist wir prüfen wieder ob die 53 der 67
3:21 entspricht nein das heißt wir schauen ist die 67 größer als 53 ja das heißt wir müssen mit dem rechten teilarray weiter Arbeiten schieben also den
3:31 linkszeiger auf den Wert hinter dem Element das wir als Mitte bestimmt haben also auf 6 und haben damit ein Array das nur noch ein Element
3:41 enthält auch dafür machen wir das was wir bisher gemacht haben wir bilden den Mittelwert zwischen links und rechts 6 + 6 S 12
3:49 2 sind 6 dann prüfen wir ob 67 mit 67 übereinstimmt ja das ist der Fall also setzen wir die Position auf den Index des Treffers und beenden den Algorithmus
4:03 hätten wir an der Stelle keinen Treffer gehabt also z.B wenn der Suchschlüssel 70 gewesen wäre dann hätten wir geschaut 70 ist größer als 67 das heißt wir
4:12 hätten versucht im rechten Teilfeld einen Treffer zu finden das bedeutet wir hätten den linkszeiger auf sieben gesetzt damit überholen sich die Links
4:22 und rechtszeiger wir haben also kein gültiges Teilfeld mehr das heißt der Algorithmus ist beendet und wir hatten keinen Treffer genau genauso wenn der
4:30 Suchschlüssel z.B 60 gewesen wäre 60 ist kleiner als 67 wir hätten versucht im linken Teilfeld weiter zu arbeiten also rechts auf 5 gesetzt auch hier hätten
4:42 sich links und rechts überholt wir haben kein gültiges Teilfeld der Algorithmus ist also beendet dann schauen wir uns die Laufzeit an die benere Suche hat
4:52 eine logarithmische Laufzeit in der o nototation großo von Log von N genauer gesagt logarithmisch zur Basis 2 weil wir in jedem Schritt das teilarray
5:02 halbieren und das ist eine sehr gute Laufzeit weil der Logarithmus ist eine Funktion die sehr langsam wächst anders ausgedrückt wenn man die Anzahl an
5:12 Elementen verdoppelt dann kommt ein weiterer Teilungsschritt dazu das heißt der zeitliche Aufwand bzw die Anzahl an Anweisungen wächst konstant mit jedem
5:23 verdoppelungsschritt wenn man hier z.B statt 10 20 Elemente hätte dann bräuchte man eben nur einen weiteren Schleifendurchlauf um nach der
5:33 Halbierung bei Zeh Elementen zu sein im Vergleich dazu bei der linearen Suche mit der linearen Laufzeit bräuchte man dann zehn weitere Schleifendurchläufe
5:43 weil da eben jedes Element geprüft werden muss die binäre Suche ist also deutlich besser als die lineare Suche hat aber eben diese Grundvoraussetzung
5:52 dass das Feld sortiert sein muss dann kommen wir zur Implementierung damit der Algorithmus hinpasst habe habe ich die Deklaration Initialisierung hier oben
6:02 nur kurz angedeutet wir sehen das dann auch gleich im richtigen Programm vollständig der suchwert muss eingelesen oder vorgegeben werden die Hilfsvariable
6:10 posst setzen wir auf -1 auf einen ungültigen Index links ist zunächst 0 und rechts Anzahl der Elemente -1 weil wir mit dem kompletten Array starten und
6:21 dann haben wir eine wild Schleife die solangee läuft wie links kleiner gleich rechts ist weil das ist die Bedingung für ein gültiges Teilfeld gleiches
6:30 erlaubt weil dann haben wir so wie im Beispiel eben ein einelementiges Teilfeld dann berechnen wir die Mitte indem wir links plus rechts geeilt durch
6:39 2 rechnen wenn wir integer nehmen wird automatisch abgerundet und dann prüfen wir ob if das Element in der Mitte also dateneckige Klammern Mitte gleich dem
6:50 suchwert entspricht wenn das der Fall ist setzen wir die Position auf die Mitte und beenden die Schleife mit einem Break ansonsten prüfen wir ob der
6:59 suchwert größer ist als der Wert in der Mitte falls ja müssen wir mit dem rechten Teilfeld weiterarbeiten wir setzen also links auf das erste Element
7:10 hinter der mitteomex her also Mitte + 1 anonsten ist der suchwert kleiner als der Wert in der Mitte das heißt wir wollen mit dem linken teilfeldbeiten
7:21 müssen also den rechtszeiger auf das letzte Element vorte setzen vom Index her mitte1 Reen dann schauen wir uns das ganze noch als
7:32 vollständiges Programm an wir haben unser Feld mit den Daten wir haben die Variable für den suchwert der wird hier eingelesen mit ReadLine die Position
7:43 setzen wir auf -1 links wird mit ull initialisiert rechts mit der Länge des Feldes -1 also dem letzten gültigen Index und Mitte wird erstmal nur
7:53 deklariert und dann kommt unsere Schleife unser eigentlicher Algorithmus while links kleiner gleich rechts wir berechnen den Mittelwert prüfen ob der
8:04 Wert in der Mitte dem suchwert entspricht setzen gegebenenfalls die Position auf die Mitte beenden die Schleife und ansonsten wenn der suchwert
8:13 größer ist als der Wert in der Mitte dann arbeiten wir mit dem rechten Teilfeld weiter ansonsten arbeiten wir mit dem linken Teilfeld weiter und auch
8:22 hier wie bei der linearen suche als einfachste Verarbeitung der Position geben wir einfach aus ob wir einen Treffer hatten oder nicht also wenn die
8:31 Position immer noch -1 ist dann haben wir keinen Treffer und ansonsten haben wir einen Treffer und geben die Position aus und wenn wir jetzt z.B die 67 vom
8:43 Beispiel suchen dann wird er die finden auch an der richtigen Position 0 1 2 3 4 5 6 das passt und wenn wir einen Wert suchen der nicht existiert wie z.B die
8:55 70 dann erhalten wir nicht gefunden das war's zur binären Suche