Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Binäre Suche (Beispiel, Laufzeit & Umsetzung in Java)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 54 Zeilen
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Nachkommastellen ohnehin abgeschnitten das heißt hier abzurunden ist die natürlichere Variante und an der Position 4 haben wir den Wert 50 den
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Elementen verdoppelt dann kommt ein weiterer Teilungsschritt dazu das heißt der zeitliche Aufwand bzw die Anzahl an Anweisungen wächst konstant mit jedem
- verdoppelungsschritt wenn man hier z.B statt 10 20 Elemente hätte dann bräuchte man eben nur einen weiteren Schleifendurchlauf um nach der
- 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
- 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
- dass das Feld sortiert sein muss dann kommen wir zur Implementierung damit der Algorithmus hinpasst habe habe ich die Deklaration Initialisierung hier oben
- nur kurz angedeutet wir sehen das dann auch gleich im richtigen Programm vollständig der suchwert muss eingelesen oder vorgegeben werden die Hilfsvariable
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- müssen also den rechtszeiger auf das letzte Element vorte setzen vom Index her mitte1 Reen dann schauen wir uns das ganze noch als
- 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
- 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
- deklariert und dann kommt unsere Schleife unser eigentlicher Algorithmus while links kleiner gleich rechts wir berechnen den Mittelwert prüfen ob der
- Wert in der Mitte dem suchwert entspricht setzen gegebenenfalls die Position auf die Mitte beenden die Schleife und ansonsten wenn der suchwert
- 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
- 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
- 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
- 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
- 70 dann erhalten wir nicht gefunden das war's zur binären Suche
Zum Nachlesen
Binäre SucheDie binäre Suche ist ein Algorithmus, der in einem Array sehr effizient ein gesuchtes Element entweder findet oder dessen Vorhandensein zuverlässig …
Lineare SucheLineare Suche ist ein Algorithmus, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist der einfachste Suchalgorithmus überhaupt.
ShakersortDer Begriff Shakersort bezeichnet einen stabilen Sortieralgorithmus, der eine Menge von linear angeordneten Elementen (z. B. Zahlen) der Größe nach sortiert …