Video 6-5: Binäre Suche

0:03 Zum Fast Abschluss ähm möchte ich noch mal ein Beispiel machen, wo wir auch noch mal auf die Analyse schauen und aber insbesondere auch einfach einen Algorithmus noch mal offiziell einführen, den viele von Ihnen wahrscheinlich kennen, aber den wir in den Übungen auch verwenden wollen.

0:20 Und in der in Erwartung, dass viele den schon kennen, machen wir das einfach erstmal als Frage, ne? Wenn sie eben gut aufgepasst haben, ist die Frage fast schon zu beantworten ohne Vorwissen. M.

2:12 Ein paar mehr soll es noch sein. Die Leute zu Hause noch mitzählt. Also, wenn Sie es nicht wissen, ist okay. Sie müssen es noch nicht wissen. Ich erkläre Ihnen ja gleich, warum es hier geht. Wenn aber alle sagen würden, äh kennen wir schon langweilig, bitte schnell weiter, dann würde ich es halt bisschen straffen.

2:42 Gut, scheint sich so langsam ah passt zu stabilisieren. Äh, es könnten theoretisch also in in Summe mit Livestream hier, wenn das alles einz einzelne Leute sind, noch ein paar mehr werden, aber ich will es nicht zu sehr in die Länge ziehen. Äh, viele von ihnen das ja auch richtig. Und der spannende Punkt ist aber so ein bisschen, dass zwar die häufigste Antwort korrekt ist, aber doch auch weit weg von der Hälfte, mehr bei einem Drittel, ne? Das heißt, wir machen das in aller Ruhe, damit Sie hinterher auf jeden Fall diese diesen Algorithmus kennen. Der ist wichtig und der ist essentiell und natürlich müssen Sie auch seine Laufzeit kennen als Informatiker. Ganz klar.

3:29 Ähm, worum geht's? Das Problem, mit dem wir uns in diesem Abschnitt beschäftigen, ist ein einfaches. Wir suchen ein Element in einer Liste und Liste für uns ist einfach ein Array, ein Array von Zahlen, um es einfach zu halten, auch wenn das der Algorithmus allgemeiner ist. Also, wir haben ein Array der Länge n gegeben mit irgendwelchen Zahlen drin und eine weitere Zahl x, die wir in diesem Array suchen wollen. Und die konkrete Formulierung davon ist, wenn diese Zahl in diesem Array vorkommt, dann hätten wir gerne den kleinsten Index i, s dass da diese Zahl steht. Oder falls nicht, dann geben wir n zurück als ein möglicher Fehlerwert und das ist so ein bisschen die C++ Konvention, dass man quasi über das Ende des Arrays hinausgelaufen ist. Äh, also einfach nur irgendeine Art, um zu markieren, dass das Element nicht vorkam. Wenn wir jetzt äh über dieses Array sonst nichts wissen, dann bleibt uns nichts anderes übrig, als alle Stellen durchzuprobieren. Und da wir den kleinsten Index wollen, macht Sinn von links anzufangen.

4:41 Das ist erstmal nicht binäre Suche, das ist die lineare Suche. Ähm, wie der Name auch schon andeutet, ähm nicht logarithmisch in der Laufzeit. Hier ist ein Beispiel mit äh Zahlen. Ich traue mich fast schon nicht, das mit ihnen zu machen, aber lass uns mal machen. Wir suchen die 69. Da ist sie nicht. Da ist sie nicht. Da ist sie nicht. Da ist sie. Das heißt, ich gebe den Wert 9 zurück und dann bin ich fertig. Wie Sie schon gesehen haben, das ist relativ langsam, wenn das Array lange ist. Nichtsdestotrotz ähm kann man das manchmal nicht umgehen. Hier ist Java Code dafür, der das Offensichtliche tut. Ähm ich habe einen Zeiger I, der das tut, was ich mit meinem Stift eben getan habe. Läuft von links durch das Array. Und wenn ich das diesen Wert, den ich suche, an der Stelle finde, dann gebe ich dieses I zurück. Weil ich die ganze Schleife durchlaufen habe, ohne das zu finden, könnte ich hier sogar I zurückgeben, weil das ja jetzt auch n ist.

5:51 sozusagenweise könnte man da auch I zurückgeben, aber ich kann auch n schreiben, damit es klarer ist. Komplizierter Algorithmus. Gut. Ähm, wenn man formal begründen wollen würde, warum der korrekt ist, könnte man als Invariante für diese Schleife ansetzen, dass äh immer wenn wir mit der Schleife beginnen, dieser Präfix der ersten I-Elemente das X nicht enthält. Und dann machen wir diesen Präfix, über den wir das wissen, eins größer und wir hören auf, sobald wir das nicht mehr können und geben dann den passenden Wert zurück. Umgekehrt, wenn X gar nicht vorkommt, dann passt diese Invariante auch. Dann ist das ganze Array gemeint, weil I dann n ist. Also noch mal ein schöner Grund, warum die Konvention ganz bequem ist an der Stelle. Lassen Sie uns auch kurz die Laufzeit analysieren. Wie wir das jetzt lange gemacht haben, legen wir dafür für die mathematische Analyse ein Kostenmodell fest. Also zählen wir die Array Zugriffe. Z.B. könnten wir hier ähm für den Rückgabewert I festhalten, dass wir genauso viele Array Zugriffe machen, wie der Wert angebex, den wir zurückgeben.

7:07 Und dementsprechend ist es im worst case n, dann habe ich das ganze Array durchlaufen müssen. Im besten Fall habe ich direkt an der ersten Stelle ein Treffer. Na ja, und unter der Annahme, dass alle Positionen, die ich zurückgebe, gleich wahrscheinlich sind, ist der der Average Case als Mittelwert eben die Mitte NHBE. Äh Sumarum ist das ein Verfahren, das einfach äh für lange Listen nicht wirklich praktikabel ist.

7:36 Aber gut, das Beste, was wir tun können, wenn wir sonst keine Annahmen über A treffen können. Was hat's also mit der binären Suche auf sich? Schöne Überleitung dann auch in das nächste Kapitel. Wenn unsere unser Eingabearrays sortiert ist, dann können wir diese Suche massiv beschleunigen. Ansonsten ist das Problem identisch. Ja, sie sehen, da hat sich nichts geändert. Wir haben nur eine zusätzliche Annahme bekommen. Und ähm am Beispiel gezeigt, warum das hilft, erklärt auch den Algorithmus. Wir suchen wieder nach 69. Diesmal ich habe die gleichen Zahlen hier, aber das Array ist jetzt sortiert. Dann kann ich in die Mitte springen, dem ich den Mittelwert der äh Indizes bilde, denn die den Bereich beschreiben, der noch interessant ist. Initial weiß ich überhaupt nichts über mein Array. Das heißt, das ganze Array ist der mögliche Bereich. Die Mitte davon ist hier die Position 7. Da prüfe ich, ist der Wert hier 63 größer oder kleiner als meine gesuchte Zahl? Weil das hier kleiner ist und das Array sortiert ist, sind auch alle Zahlen links davon noch kleiner und erst recht nicht die gesuchte Zahl. Das heißt, die kann ich alle ausschließen und formal mache ich das, indem ich diesen linken Randzeiger auf die Position rechts von meinem aktuell geprüften Wert setze. Und damit habe ich um und bei den Bereich, den ich noch betrachten muss, halbiert.

9:08 Um und bei nur weil ich runden muss und keine halben Zellen übrig lassen kann. Aber es ist hier in dem Fall sogar genau halbiert, ne? Und dann mache ich das gleiche wieder. Ich habe jetzt einen neuen Bereich, eine neue Mitte. Ich prüfe wieder, ist die 80 größer oder kleiner als meine 69? Die ist größer. Das heißt, alles zur rechten von der 80 inklusive der 80 selbst ist zu groß, kann ich wieder eliminieren. Und übrig bleiben diese drei Zahlen. Gegen Ende ist binäre Suche so ein bisschen unfassbar quälend langsam, aber wenn man das systematisch weiter durchzieht, würde man wieder den Mittelwert bilden. Die 77 ist zu groß. Das heißt, der der Teil fliegt raus und jetzt haben wir einziges Element, das noch in Betracht kommt. Und da müssen wir aber noch mal prüfen, ob das denn auch die 69 ist. Hätte ja auch also ich 68 sein können. Und dann finden wir die Zahl. Einfacher Algorithmus ist das, was man immer macht, wenn man von Hand sucht mit so ein bisschen Heuristik. Äh, weiß nicht, wer hat denn noch mal in einem gedruckten Telefonbuch eine Telefonnummer nachgeschlagen? Ich weiß, dass niemand mehr die Dinge irgendwie überhaupt zu Hause Dinger. Da habt ihr es jemals irgendwo gemacht?

10:28 Ein paar Nicken, da macht man so ein bisschen oder gleiches Spiel in einem gedruckten Wörterbuch ein Wort nachlagen. Ja, man macht so ein bisschen binäre Suche, aber nicht ganz streng. Man schätzt vielleicht ab, wo könnte ungefähr der richtige Anfangspunkt sein, statt immer in die in die Mitte strengen zu springen. Aber um weiß das, was man auch von Hand machen würde, wenn man weiß, dass eine Liste sortiert ist. Ähm, Trivial zu implementieren, nun na ja, ähm hat eine Weile gedauert, bis es den ersten backfreien Code war. Die Geschichte dahinter kenne ich nicht. Äh, sie können noch nachlesen, was hier passiert ist äh erst vor 20 Jahren. Ha, das klingt jetzt auch schon alt, aber man sollte meinen, dass nach dieser langen Zeit solche groben Schnitzer in weit verbreiteten Bibliotheken nicht mehr vorkommen, aber es ist ein subtiler äh Integer Overflow, der passieren konnte. Hier ist eine Variante, die korrekt ist, ohne Overflow und ohne Bugs. So, die Hoffnung. Ähm, wir haben also diese diese Bereiche L bis R. Das ist der Bereich, der aktuell noch in Betrachtung steht. Der ist hier so wie im Beispiel ähm hier gewählt mit sowohl L als auch R sind inklusive, ne?

11:51 Deswegen fängt er aber n -1 an. Solange dieser Bereich nicht nur ein einzelnes Element ist oder sogar leer, wenn das x, wenn das Element, das wir suchen, gar nicht vorkommt, berechnen wir den Mittelpunkt zwischen den beiden und prüfen dann, ob der Wert an der Stelle im Array kleiner oder größer als x ist. Wenn der Wert hier größer ist, dann wissen wir alles, was noch größer ist, können wir ausschließen. Dementsprechend können wir die obere Grenze nach unten schieben. Umgekehrt, wenn das Element an dieser Stelle schon zu klein ist, dann kann ich alles, was noch kleiner ist, ignorieren. Also die linke Grenze hochschieben. Und ansonsten habe ich weder das noch das, dann ist aber a von m = x. Dann kann ich diesen diese aktuelle Position zurückgeben.

12:41 Das ist der Fall, der hier beschrieben ist. Äh wieder als Invariante formuliert heißt es, der Wert, den wir suchen, liegt zwischen diesen L und R Bereichen. Liegt im aktuell noch betrachteten Bereich.

12:56 Und das gleiche gilt dann eben auch für den Index, den wir suchen, weil das Array sortiert ist. Ähm, interessanterweise kann der gleiche Code auch handhaben, wenn diese dieser Wert X nicht vorkommt. Das wird dieser zweite Fall hier zum äh Vorschein. Dann habe ich ähm immer einen dieser beiden Fälle, aber die Wild Schleife wird verlassen, weil sich diese Pointer tatsächlich überkreuzt haben und dann kann man sich überlegen, dass L zurückgeben das Richtige tut.

13:28 Also, ich hoffe, ähm, dass klar geworden ist, wie der Algorithmus funktioniert. Die Details vom Code sind tatsächlich ein bisschen fummelig. Ähm, da hilft's nichts als sich ein paar Beispiele mit den genauen ITCs mal anzuschauen. Und es ist nicht viel Code, es ist nicht ähm nicht besonders viel Variabilität hier drin. Ähm, man kann diese Berechnung von M falsch machen. Das ist das, worauf sich dieser Back hier bezogfälle verhauen, was man hier zurückgibt. Das sind so die zwei die zwei Stellen, an denen es schiefgehen kann.

14:14 Wenn wir erstmal glauben, dass der Algorithmus das tut, was hier in den Invarianten beschrieben steht, dann ist der Fokus vom aktuellen Kapitel ja noch die Analyse und die möchte ich gerne noch mit Ihnen machen.

14:30 Da gibt's z auch eine Folie, wo das aufgeschrieben ist, aber ich denke, es ist das ist hilfreich, wenn wir uns das noch einmal Stück für Stück anhand vom Code herleiten und vielleicht nehme ich mir den einfach noch mal mit äh was ich versuche werde ist an die einzelnen Zeilen wieder dran zu schreiben, welchen Beitrag die liefern, wie oft sie ausgeführt werden. Äh wir können uns auf ein abstraktes Kostenmaß einigen.

15:18 Und das muss etwas sein, was in der innersten Schleife passiert. Und relativ bequem, weil es dann diese beiden äh möglichen Fälle vereint ist, die Anzahl Vergleiche zu zählen.

15:34 Und wir sind hier mal großzügig und zählen die beiden Vergleiche sozusagen als einen. Die Idee dabei ist, dass man ähm um es hier kompakt im Code zu schreiben, habe ich das nicht getan. Aber wenn man andere Objekte hätte, dann werden wir im nächsten Kapitel eh noch drüber reden, ist es oft eine Operation, die prüft, ob ein Element X kleiner ist als was, größer oder gleich. Wenn das Zahlen sind, ist es eigentlich eine Subtraktion und dann prüfe ich das Vorzeichen. So würden das auch äh die die Instruktionen in der CPU machen. Das heißt, diese zwei Zeilen ähm Zeile 6 und 7, die zählen wir als 1.

16:28 Das macht die Analyse auch dann einfacher, weil wir nicht unterscheiden müssen, welcher der beiden Fälle eingetreten ist. Dementsprechend sind die Teile davor hier umsonst. Das heißt, eine Ausführung dieser Wildschleife hat konstante Kosten. Und die Frage ist im Wesentlichen, wie oft muss ich diese Schleife durchlaufen?

17:08 Nach unserem Schema von äh diverse Folien vorher ist das jetzt ähm und dann kommt hier dieser sonst Code, den wir schon analysiert haben. Wir wissen schon, dass das ein Laufzeit konstant ist oder genau eins ist, wenn wir diese Vergleiche zählen wollen. Äh und der setzt aber auch L und R um. Für die Laufzeit und wir können das ineinander überführen. Oh oh. Also Ziel ist ähm zu übersetzen zwischen diesen zwei Parametern in einen. Und das gelingt uns, indem wir n als die Differenz der beiden setzen. Genauer genommen die Anzahl Elemente dazwischen. Und da die beide inklusive sind, kommt dann +1 dazu. Dann haben wir hier ein A von N. Wenn man sich jetzt anschaut, was äh mit den mit den Grenzen passiert, dann wird das ähm aus meinem L bis R, worus ich dieses M berechne, wird entweder nur dieser Teil oder nur dieser Teil entweder dann das neue Lich hier sitzt oder das neue Rich hier.

18:51 In beiden Fällen ist das, was äh was ich daraus generiere, höchstens halb so groß wie das bisherige Array. Also da drin wird n zu einem n Strich, das wir nicht ganz genau wissen, aber es ist höchstens n halbe. Der worst case ist sozusagen ein ungerades N. Dann ist dieses M, das ist genau die Mitte, ein gerades N, dann ist das M ein bisschen links von der Mitte. Der Bereich rechts davon sind genau n halbe Elemente.

19:34 Das ist so der ähm der Fall, den wir haben. Das heißt, ganz präzise können wir die Laufzeit nicht mit dem Master Theorien lösen. Man kann die Hand haben in dem Fall, aber äh das wollen wir an der Stelle gar nicht tun. Wir haben die Laufzeit für den inneren Teil, wissen wir schon, ist konstant und wir haben dazu den rekursiven Teil oder den nächsten nächste Schleifeniteration mit t von nbe und das ist eine obere Schranke.

20:17 Lassen Sie uns statt Allgemeinzeit lassen Sie uns das hier als Anzahl Vergleiche machen. Dann können wir präzise Zahlen einsetzen und wieder Anzahlvergleiche gemeint in diesem äh drei Wege Vergleich.

20:34 Dann habe ich diese Rekursion. Jetzt fehlt noch eine Abbruchbedingung. Wann höre ich auf? Na ja, wenn äh wenn das hier nicht mehr erfüllt ist, wenn L = R ist, dann habe ich R - L + 1 immer noch 1. Und für diesen Fall breche ich die Schleife ab. Das heißt, da habe ich keinen weiteren Vergleich.

20:59 Und jetzt erinnern Sie sich vielleicht, dass das genau auf unser Master Theoremen passt. Wir haben eine eine Funktion hier ohne Wachstum, also n hoch 0. Und das müssen wir vergleichen mit dem einen rekursiven Aufruf der Größe ein/H/B. Das heißt, dieses C, was wir berechnen, ist log zur Basis von dieser Inneren Konstante von 1. Das ist natürlich 0. Egal von welcher Basis, log von 1 ist 0, die Basis äh ja für nicht degenerierte Basiswerte. Und das heißt, wir vergleichen für das Wachstum unsere Funktion f von n vergleichen wir mit n hoch c, also konstant.

22:01 Und an der Stelle wachsen die gleich schnell. Das heißt, wir sind in diesem zweiten Fall von Master Theorem. Und in dem Fall war dann die Gesamtkosten t von nθ von dem Wachstum dieser Funktion mal log n und das konstant ist nur log n.

22:27 Also eine mögliche Analyse, die uns zumindest die korrekte äh Tetaklasse gibt, folgt direkt aus dem Master Theorien. Der einzige Kniff, der nötig ist hier ist eine eine Umformulierung. Die Variablen, die wir im Code haben, sind nicht direkt die Eingabegröße, sondern es ist ein Bereich von bis das eine ähm häufig vorkommende Sache. Das heißt, das können Sie im Kopf behalten. Wenn Sie auf Teilbereichen von dem Array arbeiten, dann ist es ist es oft zielführend. statt dieser zwei Parameter dann die Differenz anzuschauen und zu prüfen, ob das eine sinnvolle Größe ist, die in jedem Schritt kleiner wird. Der zweite Kniff war hier, dass wir nur eine obere Schranke für die Laufzeit bekommen, weil dieses halbieren manchmal ein bisschen besser noch ausgeht. Manchmal ist die die Eingabe, die verbleibt, ein bisschen weniger als die Hälfte durch die Rundungsfehler. Ähm, wie damals besprochen für die für die Theterklasse im Master Theorem mit üblichen Funktionen wie hier der Konstante macht das keinen Unterschied.

23:33 Man kann in diesem Fall, weil das ein besonders einfacher Algorithmus ist, auch ein bisschen genauer hinschauen, die die Rekursion von Handlösen. Das ist hier ausgeführt. Dann bekommt man nicht nur log n als theter Klasse, sondern präzise Basis zweier Logarithmus zur Bas logarithmus von n + 1 an vergleichen als obere Schranke. Ähm gleiche Definition, was Vergleiche äh heißt, wie wir es eben gemacht haben. Gleiche Rekursion im Wesentlichen mit dem Argument von eben. Aber jetzt statt Masterheoremen einfach die Rekursion iterieren, mehrmals ineinander einsetzen, dann sieht man, dass man hier immer eine einzu gewinnt und das n um ein Faktor 2 schrumpft, bis wir am Ende bei der Anfangsbedingung angekommen sind. Ah, die haben sie hier auf eins gesetzt. Äh, warum auch immer, hätte ich jetzt gesagt, ist kein Vergleich mehr.

24:39 Ähm dementsprechend kriegt man dann hier durch zählen, wie oft man enhalbieren muss, bis man bei 1 angekommen ist, den Logend Beitrag. M.