https://youtu.be/236QQsjvehw
1. Einführung
Stelle dir vor es ist ein ganz normaler Tag und du möchtest dich in deinem Facebook-Account anmelden. Wie du sicherlich weißt, hat Facebook weltweit über 1.5 Milliarden Nutzer. Wenn du deine Zugangsdaten eingegeben hast, muss im Hintergrund geprüft werden, ob diese korrekt sind. Hierzu wird nach deinen bei Facebook gespeicherten Benutzerdaten in einer Datenbank gesucht. Damit nicht alle 1.5 Milliarden Einträge nacheinander durchgesucht werden, muss der im Hintergrund laufende Suchalgorithmus effizient vorgehen, da du sonst mehrere Sekunden bis Minuten warten müsstest, bis du Zugang zu deinem Account hast (und das wäre ziemlich lästig). Deshalb zeige ich dir eine clevere Technik, mit der du schnell nach Informationen suchen kannst: Die binäre Suche.
Die binäre Suche ist ein Algorithmus, mit dem du in kurzer Zeit Informationen in einer sortierten Liste suchen kannst. Wie kurz, wirst du noch sehen. Wichtig ist, dass die Liste, in der du suchst, sortiert ist, da der Algorithmus sonst nicht funktioniert. Der Algorithmus erhält als Eingabe also eine sortierte Liste von Elementen und ein Element, das gesucht werden soll. Wenn das gesuchte Element in der eingegebenen Liste enthalten ist, dann liefert der Algorithmus die Position zurück, an der es sich in der Liste befindet. Ansonsten teilt er mit, dass das Element nicht gefunden wurde (wie genau er das macht, hängt von der entsprechenden Programmiersprache ab; oft verwendet man dafür den Wert 'null'). Wie sollte Facebook in seiner alphabetisch sortierten Liste mit Benutzernamen und Passwörtern vorgehen, wenn es den Benutzer 'mathisfun' finden möchte? Statt einfach von vorne alle Listenelemente durchzuklappern, ist es sinnvoll irgendwo in der Mitte anzufangen, da der Buchstabe 'm' mittig des Alphabets zu finden ist.
2. Das Zahlen-Rate-Spiel
Mit Buchstaben zu hantieren ist für das Verständnis erstmal kontraproduktiv, da du in der Schule wahrscheinlich ein Beispiel mit Zahlen kennenlernen wirst. Beachte aber, dass sich Buchstaben durch ihre Position im Alphabet auch in Zahlen ausdrücken lassen. Stelle dir also lieber ein einfaches Ratespiel vor: Ich denke mir eine Zahl zwischen 1 und 100 (inklusive 1 und 100) und du errätst, welche Zahl ich mir ausgedacht habe. Du musst meine Zahl mit möglichst wenigen Versuchen erraten. Ich gebe dir maximal 7 Versuche! Wenn du die Zahl nicht triffst, sage ich dir, dass sie entweder größer oder kleiner als die von dir genannte Zahl ist. Wenn du sie triffst, sage ich dir, dass du sie richtig erraten hast.
Nehmen wir mal an, ich habe mir die 42 ausgedacht. Du rätst als erstes die 1. Ich sage dir, "meine Zahl ist größer". Nun rätst du die 2 und ich sage dir "meine Zahl ist größer". Dann rätst du die 3 und ich sage dir wieder, dass meine Zahl größer ist. Wenn du so naiv weiter rätst, wird nach der 7 Schluss für dich sein, da du maximal 7 Versuche hast, die Zahl zu erraten. Du bräuchtest mit dieser Methode 42 Versuche, um auf meine Zahl zu kommen! Das muss doch besser gehen!
Hier kommt jetzt die binäre Suche ins Spiel. Du rätst diesmal als erstes die Zahl in der Mitte zwischen 1 und 100, nämlich die 50. Jetzt sage ich dir, dass meine Zahl kleiner ist. Du hast so bereits die Hälfte aller Zahlen ausgeschlossen. Jetzt rätst du die Zahl genau in der Mitte zwischen 1 und 50, also die 25. Ich sage dir nun, dass meine Zahl größer ist. Nun hast du wieder die Hälfte der noch verbliebenen Zahlen ausgeschlossen. Jetzt rätst du die Zahl zwischen 25 und 50, also die 38. Ich antworte dir, dass meine Zahl größer ist. Von den verbliebenen Zahlen hast du wieder die Hälfte ausgeschlossen. Jetzt rätst du die Zahl zwischen 38 und 50, also die 44. Jetzt sage ich dir, dass meine Zahl kleiner ist. Erkennst du bereits ein Muster? Jetzt rätst du die Zahl zwischen 38 und 44, also die 41 und ich antworte dir, dass meine Zahl größer ist. Nun rätst du also die Zahl zwischen 41 und 44, also die 43 und ich sage dir, dass meine Zahl kleiner ist. Da du schlau bist, weißt du nun, dass meine Zahl zwischen 41 und 43 liegt und deine Antwort lautet 42. Jetzt bekommst du endlich die Antwort, die du hören wolltest, nämlich, dass du meine Zahl erraten hast. Statt der 42 Versuche, die du mit der naiven Methode gebraucht hättest, hast du nun nur 7 Versuche benötigt. Wenn du in einer sortierten Liste mit 100 Elementen mit der binären Suche suchst, wirst du immer maximal 7 Versuche brauchen, d. h. wenn du unter diesen Voraussetzungen (also einer sortierten Liste mit 100 Elementen) suchst, kannst du gar nicht verlieren.
3. Versuchsanzahl und Listenlänge
Doch wie viele Versuche würdest du brauchen, wenn ich eine Zahl zwischen 1 und 1000 statt zwischen 1 und 100 wählen würde? Mit der naiven Methode bräuchtest du im Worst-Case (also im "schlimmsten Fall") 1000 Versuche. Denn wenn ich die 1000 wähle und du dich von vorne durchzuraten versuchst, wirst du 1000 Versuche bis zu meiner Zahl brauchen. Nun, bei 100 Elementen brauchst du mit der binären Suche maximal 7 Versuche. Sind es bei 1000 Elementen dann 7 mal 10 also 70 Versuche, weil du 10 mal so viele Elemente hast, in denen du suchst? Nein! Mit jedem Rateversuch reduzierst du die Anzahl der übrig gebliebenen Möglichkeiten um die Hälfte. Im ersten Versuch bleiben von den 1000 Möglichkeiten nur noch 500 übrig. Danach nur noch 250. Dann nur noch 125, 63, 32, 16, 8, 4, 2 und schlussendlich nur noch eine. Du benötigst also maximal 10 Versuche, denn es kann ja sein, dass du die Zahl schon vorher errätst. Obwohl sich die Anzahl der Elemente verzehnfacht hat, brauchst du nur maximal 3 Versuche mehr. Wow! Das ist effizient, oder?
4. Laufzeit der binären Suche
Gibt es eine Möglichkeit zu berechnen, wie viele Versuche maximal für eine sortierte Liste mit \(n\) verschiedenen Elementen benötigt werden? Ja, die gibt es! Da sich die Anzahl der übrig gebliebenen Elemente mit jedem Rateversuch um die Hälfte reduziert, sind maximal \(\log_{2}{(n)}\) Versuche nötig. \(\log_{2}{(n)}\) ist der Logarithmus von \(n\) zur Basis \(2\). Dieser gibt eine Antwort auf die Frage "Wie oft muss ich die \(2\) mit sich selbst multiplizieren, um auf \(n\) zu kommen?" Der Logarithmus ist die Umkehrfunktion zur Exponentialfunktion. Testen wir diese Formel doch einfach mal für \(n=100\) (also unserem ersten Zahlen-Rate-Spiel): Der Logarithmus von \(100\) zur Basis zwei, gibt eine Antwort auf die Frage, wie oft man die \(2\) mit sich selbst multiplizieren muss, um auf \(100\) zu kommen. Die Antwort lautet (nach oben gerundet, da es keine gebrochene Anzahl an Versuchen gibt) \(7\) mal! Für unser zweites Zahlen-Rate-Spiel gilt: Der Logarithmus von \(1000\) zur Basis zwei, gibt eine Antwort auf die Frage, wie oft man die \(2\) mit sich selbst multiplizieren muss, um auf \(1000\) zu kommen. Die Antwort lautet (gerundet) \(10\) mal!
\(\log_{2}{(n)}\) ist die sogenannte Laufzeit der binären Suche. Du kannst mal verschiedene Werte für \(n\) einsetzen und vergleichen, wie langsam das Ergebnis ansteigt. Algorithmen sollten effizient laufen und wenn du für immer größer werdende Eingabewerte nur einen logarithmischen Anstieg zu verzeichnen hast, ist das weitaus effizienter als die Anstieg bei dem naiven Algorithmus, bei dem du einfach vorne zu zählen beginnst. Hierfür brauchst du im Worst-Case ja \(n\) Versuche. Verglichen mit dem logarithmischen Anstieg erkennst du, dass für immer größere Listen ein gewaltiger Laufzeitunterschied entsteht!
Dieser Artikel hat 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.
