# 3.2 Binäre Suche Quelle: https://inf.zone/lectures/3-algorithmen/short-3-2-binaere-suche/ ## Video [Video ansehen (1080p)](https://videos.inf.zone/e6ae8382beddfc76/short-3-2-binaere-suche-1080p.mp4) · [Video (720p)](https://videos.inf.zone/e6ae8382beddfc76/short-3-2-binaere-suche-720p.mp4) · [Video (480p)](https://videos.inf.zone/e6ae8382beddfc76/short-3-2-binaere-suche-480p.mp4) · [Video auf YouTube](https://youtu.be/vRcepVVlvrQ) ## Hinweise zu diesem Video **Korrekturen** Die Korrekturen betreffen das Video. In den Folien zum Herunterladen sind sie eingearbeitet, soweit sie die Folien betreffen. - Folie 28: Die Regel „log2(n) aufrunden“ stimmt für 20 Elemente, aber nicht allgemein. Richtig ist: log2(n) abrunden und 1 addieren; bei 16 Elementen sind es also höchstens 5 Vergleiche, nicht 4. - Ton zu Folie 26: Für eine einzige Suche lohnt sich vorheriges Sortieren nicht, denn schon das Sortieren muss jedes Element mindestens einmal ansehen, die lineare Suche höchstens jedes einmal. Sortieren zahlt sich erst aus, wenn mehrfach gesucht wird. **Einordnung** - Welches Element bei gerader Anzahl die Mitte ist, klärt erst Frage 1 der Extra-Minuten (Folie 28): Sie können ab- oder aufrunden, müssen aber dabei bleiben. Das brauchen Sie, um die binäre Suche von Hand durchzuspielen. ## Material - [Folien](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf) - Folien und Transkript: unten auf dieser Seite ## Folien und Transkript *Folientext aus den PDF-Folien, darunter jeweils der gesprochene Text des Videos. Der gesprochene Text ist maschinell transkribiert und nachkorrigiert, kann aber noch Fehler enthalten; im Video sprechen abwechselnd Prof und eine AI-Figur, die Sprecherwechsel sind nicht markiert. Die Zuordnung zu den Folien ist ungefähr. Die Zeitangaben verlinken auf die Stelle im Video (YouTube). Maßgeblich sind Video und Folien.* ### Folie 1 — Binäre Suche [Folie 1 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=1) #### Transkript **[Video 00:00–00:32](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=0)** Dies ist Inf-Einf-B. Heute binäre Suche. Bevor wir anfangen, was ist deine Lieblingsfarbe für Socken? Ich habe da keine Vorliebe. Und die zweitliebste? Hä? Ich habe auch keine zweitliebste Sockenfarbe. Und warum ist das überhaupt wichtig? Schade. Für unser heutiges einführendes Beispiel hätte ich etwas mit sortierten Socken gemacht. Hä? Was haben sortierte Socken mit binärer Suche zu tun? Leg jetzt mal los. Du wirst schon sehen. Ich kann auch ohne Socken ins Thema einführen. ### Folie 2 [Folie 2 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=2) Bei der Binären Suche besteht die Idee des Algorithmus darin, nach dem Prinzip „Teile und herrsche“ vorzugehen, indem der Suchbereich jedes Mal halbiert wird, um ein gesuchtes Element zu finden. Allerdings ist die Vorausstzung, dass unser Array bereits sortiert ist. #### Transkript **[Video 00:32–01:02](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=32)** Die binäre Suche ist ein Algorithmus zum Suchen eines bestimmten Elements in einem Array. Die Grundidee ist dabei, das Suchgebiet bei jedem Schritt zu halbieren, um einen Zielwert zu finden. Um diese Methode nutzen zu können, muss unser Array jedoch zuerst sortiert sein. Nur dann können wir Annahmen über den Inhalt des Arrays treffen. Soweit so gut. Jetzt wäre halt ein Beispiel recht. Aber bitte kommen wir jetzt nicht mit Socken, die nach Lieblingsfarbe sortiert sind. Nein, nein. Stellen Sie sich vor, Sie haben ein Buch, in dem Sie etwas auf einer bestimmten Seite suchen. **[Video 01:02–01:34](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=62)** Anstatt jede Seite einzeln zu überprüfen, würden Sie das Buch in der Mitte öffnen und basierend darauf entscheiden, ob Sie in der vorderen oder hinteren Hälfte weitersuchen müssen. Das ist im Wesentlichen das Prinzip der binären Suche. Wir schauen uns das am besten im Pseudocode an. Der Algorithmus beginnt, indem er den Mittelpunkt des gesamten Arrays berechnet. Wenn der gesuchte Wert dort nicht gefunden wird, entscheidet er basierend auf einem Vergleich, ob er in der linken oder rechten Hälfte weitersuchen muss. Dieser Prozess wird wiederholt, wobei das Suchgebiet jedes Mal halbiert wird, bis der Wert gefunden wird oder festgestellt wird, **[Video 01:34–02:14](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=94)** Dass er nicht im Array vorhanden ist. Ein wichtiges Konzept, das der binären Suche zugrunde liegt, ist das Prinzip Teile und Herrsche oder auf Englisch Divide and Conquer. Dieses Prinzip ist fundamental für viele effiziente Algorithmen in der Informatik. Ja, das ist in der Tat ein wichtiges Konzept. Wie genau wird es eigentlich bei der binären Suche angewendet? Bei der binären Suche wenden wir das Teile und Herrsche-Prinzip folgendermaßen an: Wir teilen das sortierte Array in der Mitte und entscheiden dann, in welcher Hälfte wir weitersuchen müssen. Dadurch reduzieren wir die Problemgröße bei jedem Schritt um die Hälfte. Dieses Vorgehen wiederholen wir rekursiv auf der ausgewählten Hälfte, bis wir den gesuchten Wert finden oder feststellen, dass er nicht im Array vorhanden ist. Moment mal! **[Video 02:14–02:46](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=134)** Du verwendest den Begriff rekursiv, ohne ihn zu erklären. ### Folie 3 — Pseudocode [Folie 3 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=3) Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn sich das gesuchte Element in der Mitte befindet, bist du fertig. Andernfalls: wenn das gesuchte Element kleiner als das in der Mitte ist, wiederhole den Vorgang nachdem du den Endpunkt auf den Index gesetzt hast, der links von der Mitte ist. oder, wenn das gesuchte Element größer als das in der Mitte ist, wiederhole den Vorgang nachdem du den Startpunkt auf den Index gesetzt hast, der rechts von der Mitte ist. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:14–02:46](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=134)** Ich habe dir doch jetzt schon mehrmals gesagt, dass du keine fortgeschrittenen Konzepte verwenden sollst, die wir noch nicht behandelt haben. Entschuldigung, du hast recht. Ich meinte, wir wiederholen diesen Prozess auf der ausgewählten Hälfte, bis wir fertig sind. ### Folie 4 — Beispiel [Folie 4 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=4) 19 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:14–02:46](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=134)** Ja, schon besser. ### Folie 5 — Beispiel [Folie 5 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=5) 19 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:14–02:46](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=134)** Weiter. ### Folie 6 — Beispiel [Folie 6 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=6) 19 gesucht: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:14–02:46](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=134)** Lassen Sie uns nun ein detailliertes Beispiel durchgehen, um den Ablauf der binären Suche zu veranschaulichen. Wir werden ein Array mit fünfzehn Elementen verwenden und nach dem Wert neunzehn suchen. Zuerst müssen wir das Array sortieren. Moment, das habe ich schon einmal vorbereitet. Unser sortiertes Array sieht folgendermaßen aus. **[Video 02:46–03:06](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=166)** Sechs, sieben, acht und so weiter bis dreißig, wobei halt nicht alle Zahlen vorkommen. Wir beginnen mit dem gesamten Array. Das erste Element hat den Index null, das letzte hat Index vierzehn. Schritt eins: Wir berechnen den Mittelpunkt. Null plus vierzehn geteilt durch zwei ergibt sieben. An Index sieben finden wir den Wert fünfzehn. Ist fünfzehn unser Zielwert? ### Folie 7 — Beispiel [Folie 7 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=7) 19 gesucht: 0 Start: 14 Ende: 7 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:06–03:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=186)** Nein, 19 ist größer als 15, also müssen wir in der rechten Hälfte des Arrays weiter suchen. ### Folie 8 — Beispiel [Folie 8 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=8) 19 gesucht: 0 Start: 14 Ende: 7 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:06–03:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=186)** Schritt zwei: Wir aktualisieren unseren Startpunkt auf 8, also vom vorherigen Mittelpunkt aus, um 1 weiter rechts. ### Folie 9 — Beispiel [Folie 9 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=9) 19 gesucht: 8 Start: 14 Ende: 7 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:06–03:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=186)** Der Endpunkt bleibt 14. ### Folie 10 — Beispiel [Folie 10 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=10) 19 gesucht: 8 Start: 14 Ende: 11 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:06–03:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=186)** Wir berechnen den neuen Mittelpunkt 8 plus 14 durch 2 ergibt 11. ### Folie 11 — Beispiel [Folie 11 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=11) 19 gesucht: 8 Start: 14 Ende: 11 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:06–03:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=186)** An Index 11 finden wir den Wert 23. ### Folie 12 — Beispiel [Folie 12 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=12) 19 gesucht: 8 Start: 10 Ende: 11 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:06–03:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=186)** Ist 23 unser Zielwert? Nein, 19 ist kleiner als 23. Wir müssen also in der linken Hälfte dieses Teilarrays weiter suchen. Schritt drei: Jetzt bleibt der Startpunkt unverändert auf 8, aber wir aktualisieren den Endpunkt auf 10, direkt links vom vorherigen Mittelpunkt. ### Folie 13 — Beispiel [Folie 13 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=13) 19 gesucht: 8 Start: 10 Ende: 9 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:06–03:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=186)** Wir berechnen den neuen Mittelpunkt 8 plus 10 durch 2 ergibt **[Video 03:45–04:16](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=225)** An Index 9 finden wir den Wert 19. Ist 19 unser Zielwert? ### Folie 14 — Beispiel [Folie 14 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=14) 19 gesucht: 8 Start: 10 Ende: 9 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:45–04:16](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=225)** Ja. ### Folie 15 — Beispiel [Folie 15 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=15) 16 gesucht: 0 Start: 14 Ende: Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:45–04:16](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=225)** Wir haben den gesuchten Wert gefunden und können die Suche beenden. ### Folie 16 — Beispiel [Folie 16 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=16) 16 gesucht: 0 Start: 14 Ende: 7 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:45–04:16](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=225)** Sehen Sie, wie wir bei jedem Schritt den Suchbereich halbiert haben? Wir starteten mit 15 Elementen, reduzierten auf 7, dann auf 3 und fanden schließlich den gesuchten Wert. Dies demonstriert die Effizienz der binären Suche, besonders bei größeren Datensätzen. Ja, das klingt ja eigentlich sehr einfach. Aber du hast dir fürs Beispiel auch extra einen Wert genommen, der im Array enthalten ist. **[Video 04:16–04:34](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=256)** Was passiert denn jetzt, wenn wir zum Beispiel nach der 16 gesucht hätten? Okay, lass uns nun ein Beispiel durchgehen, bei dem das gesuchte Element nicht im Array vorhanden ist. Wir werden das gleiche sortierte Array verwenden, aber diesmal suchen wir nach dem Wert 16. Schritt 1: Der Startindex ist 0. **[Video 04:34–05:10](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=274)** Der Endindex 14, die Mitte also wieder 7. ### Folie 17 — Beispiel [Folie 17 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=17) 16 gesucht: 8 Start: 14 Ende: 7 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 04:34–05:10](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=274)** Der Wert an Index 7 ist 15. 16 ist größer, also suchen wir in der rechten Hälfte weiter. ### Folie 18 — Beispiel [Folie 18 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=18) 16 gesucht: 8 Start: 14 Ende: 11 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 04:34–05:10](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=274)** Schritt 2: Der Startindex ist nun 8, der Endindex weiterhin 14, die Mitte ist 22 durch 2 also 11. Der Wert an Index 11 ist 23. ### Folie 19 — Beispiel [Folie 19 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=19) 16 gesucht: 8 Start: 10 Ende: 11 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 04:34–05:10](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=274)** 16 ist aber kleiner als 23, also suchen wir in der linken Hälfte weiter. Schritt 3: Der Startindex bleibt daher auf 8, aber der Endindex ist nun 10, eins links neben der alten Mitte. ### Folie 20 — Beispiel [Folie 20 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=20) 16 gesucht: 8 Start: 10 Ende: 9 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 04:34–05:10](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=274)** Die neue Mitte ist 18 durch 2 also 9. Der Wert an Index 9 ist 19. ### Folie 21 — Beispiel [Folie 21 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=21) 16 gesucht: 8 Start: 8 Ende: 9 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 04:34–05:10](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=274)** 16 ist kleiner, also suchen wir in der linken Hälfte weiter. ### Folie 22 — Beispiel [Folie 22 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=22) 16 gesucht: 8 Start: 8 Ende: 8 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 05:10–05:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=310)** Schritt vier: Startindex ist weiterhin acht, Endindex ist eins links neben der alten Mitte. ### Folie 23 — Beispiel [Folie 23 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=23) 16 gesucht: 8 Start: 7 Ende: 8 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 05:10–05:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=310)** Die alte Mitte war neun, also ist der Endindex nun acht. Die Mitte von acht und acht ist acht. Der Wert an Index acht ist siebzehn. Sechzehn ist kleiner als siebzehn, also müssen wir links von der Mitte weiter suchen. Schritt fünf: Der Startindex bleibt acht, der Endindex muss wieder um eins kleiner sein als die alte Mitte, also sieben. Beachten Sie, dass der Startindex nun größer als der Endindex ist. Daran erkennen wir, dass das gesuchte Element nicht im Array vorhanden ist. ### Folie 24 — Beispiel [Folie 24 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=24) 16 gesucht: 8 Start: 7 Ende: 8 Mitte: 6 7 8 9 10 11 14 15 17 19 22 23 25 28 30 ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` Wiederhole, bis das (Teil-)Array die Größe 0 hat: Berechne den Mittelpunkt des aktuellen (Teil-)Arrays. Wenn gesuchtes Element in der Mitte ist: fertig! Andernfalls: Gesuchtes Element kleiner als das in der Mitte? Endpunkt = Index links von der Mitte. Weiter! Gesuchte Element größer als das in der Mitte? Startpunkt = Index rechts von der Mitte. Weiter! #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 05:10–05:45](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=310)** Wir haben die Suche mit einem Array von fünfzehn Elementen begonnen und konnten in nur fünf Schritten feststellen, dass das gesuchte Element ### Folie 25 [Folie 25 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=25) Fälle Worst Case: Wir müssen die n Elemente „bis zum Ende“ immer weiter halbieren, um das gesuchte Element zu finden – weil das Zielelement entweder erst am Ende der letzten Teilung gefunden wird oder gar nicht vorhanden ist. Best Case: Das gesuchte Element befindet sich in der Mitte und wird sofort, also beim ersten Vergleich, gefunden. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 05:45–06:05](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=345)** nicht vorhanden ist. Dies demonstriert erneut die Effizienz der binären Suche, selbst wenn das gesuchte Element nicht im Array enthalten ist. Die Effizienz der binären Suche ergibt sich daraus, dass wir bei jedem Schritt die Hälfte der verbleibenden Elemente ausschließen können. Dadurch reduziert sich die Anzahl der notwendigen Vergleiche drastisch im Vergleich zur linearen Suche. **[Video 06:05–06:44](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=365)** besonders bei großen Datenmengen. Im schlimmsten Fall müssen wir log zwei von n Vergleiche durchführen, wobei n die Anzahl der Elemente im Array ist. Das bedeutet, dass wir selbst in einem Array mit einer Million Elementen höchstens zwanzig Vergleiche benötigen, um ein Element zu finden oder festzustellen, dass es nicht vorhanden ist. ### Folie 26 [Folie 26 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=26) O(log n) Laufzeitkomplexität Ω(1) #### Transkript **[Video 06:05–06:44](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=365)** Kommen wir nun zur Komplexität der binären Suche. Wie ich gerade erwähnt habe, ist die binäre Suche deutlich effizienter als die lineare Suche, besonders bei großen Datenmengen. Im schlimmsten Fall müssen wir das Array log zwei von n mal halbieren, um das gesuchte Element zu finden oder festzustellen, dass es nicht im Array vorhanden ist. Dies führt zu einer Zeitkomplexität **[Video 06:44–07:23](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=404)** O von log n. Und was ist mit dem besten Fall? Im besten Fall finden wir das gesuchte Element direkt in der Mitte des Arrays beim ersten Vergleich. Das führt zu einer Zeitkomplexität von Omega von eins, also konstanter Zeit. Schon toll. Die binäre Suche ist mindestens so gut wie die lineare Suche und meistens sogar viel schneller. Schon, aber halt nur, wenn das Array schon sortiert ist. Wenn du das Array vorher noch sortieren musst, dann dauert es länger. Schon klar. Aber es gibt ja auch sehr effiziente Sortierverfahren, zum Beispiel Counting Sort, die unter bestimmten Voraussetzungen eine lineare Laufzeitkomplexität haben. Ich würde erwarten, dass es sich bei großen Arrays lohnt, sie zuerst zu sortieren und dann mit binärer Suche zu durchsuchen, selbst wenn man nur einen einzigen Wert sucht. ### Folie 27 [Folie 27 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=27) E X T R A S I N 3 M I N U T E N FRAGEN – ANTWORTEN – RÄTSEL UND KURZE ZUSAMMENFASSUNG #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 07:23–07:32](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=443)** Und wenn man öfter suchen will, dann amortisieren sich die Kosten fürs Sortieren ja sowieso. Ja, natürlich, aber und das muss ich jetzt einfach sagen: In deiner Erklärung setzt du voraus. **[Video 07:32–08:08](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=452)** Dass die Studierenden schon etwas über Sortieralgorithmen wissen. Die haben wir aber noch gar nicht behandelt. Ha! Touché. Gerade am Ende ist es aber so ein Blick über den Tellerrand doch echt auch gut. Das zeigt den Studierenden, dass es da draußen noch sehr viel mehr zu entdecken gibt. Apropos Ende: Wir sollten mal zu unseren drei Extra Minuten kommen. ### Folie 28 [Folie 28 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=28) F1: Was nimmt man als Mitte, wenn die Elementzahl im Array gerade ist? Zum Beispiel bei zwölf Elementen? F2: Wie viele Vergleiche sind bei der binären Suche maximal nötig, um einen Wert in einem Array mit 20 Elementen zu suchen? A2: 5 Vergleiche weil log2(20) = 4,32, d.h. abgerundet 4, plus 1 = 5 #### Transkript **[Video 07:32–08:08](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=452)** Was für eine Frage könnte man denn an dieser Stelle haben? Für unsere drei Extra Minuten habe ich folgende Frage vorbereitet: Was nimmt man als Mitte, wenn die Elementzahl im Array gerade ist? Zum Beispiel bei zwölf Elementen? Dann ist 0 plus 11 durch 2 ja 5,5. Aber man braucht ja eine Ganzzahl für den Index. Das ist eine gute Frage. **[Video 08:08–08:42](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=488)** Man sollte sich zwingen, immer über solche Randfälle, also Edge Cases, nachzudenken, wenn man Algorithmen entwickelt. Also, was macht man denn dann? Es gibt zwei Möglichkeiten. Entweder abrunden. Das passiert eh automatisch, wenn wir die Ganzzahldivision in C verwenden. Bei zwölf Elementen wäre die Mitte also 0 plus 11 durch 2, also 5. Alternativ können wir aufrunden, indem wir den Wert Startindex plus Endindex plus 1 durch 2 teilen. Das Plus 1 führt automatisch dazu, dass der Mittelindex aufgerundet wird. In unserem Beispiel wäre das 0 plus 11 plus 1, also 12, durch 2, was 6 ergibt. **[Video 08:42–08:58](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=522)** Beide Methoden sind korrekt und führen zu einem funktionierenden Algorithmus. Die Wahl zwischen ihnen hängt oft von der spezifischen Implementierung oder persönlichen Präferenzen ab. Wichtig ist, dass man konsistent bleibt und die gewählte Methode im gesamten Algorithmus beibehält. Außerdem muss man sicherstellen **[Video 08:58–09:34](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=538)** Dass der Algorithmus auch bei Arrays mit nur einem oder zwei Elementen korrekt funktioniert. Okay, ich habe auch eine Frage: Wie viele Vergleiche sind denn bei der binären Suche nötig, um einen Wert in einem Array mit 20 Elementen zu suchen? Wir gehen Schritt für Schritt durch. Das ist intuitiver, als einfach den Zweierlogarithmus auszurechnen. Wir haben ja gesagt, dass die binäre Suche in jedem Schritt den Suchbereich halbiert. Wir beginnen mit 20 Elementen. Erster Vergleich: Aus 20 werden 10 Elemente. Zweiter Vergleich: Aus 10 werden 5 Elemente. Dritter Vergleich: Aus 5 werden 2 oder 3 Elemente, je nachdem, wie wir runden. Vierter Vergleich: Aus den 2 oder 3 Elementen wird 1 Element. **[Video 09:34–10:13](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=574)** Der fünfte Vergleich ist der letzte Vergleich, den wir brauchen, um festzustellen, ob das verbliebene Element das Gesuchte ist. Im schlimmsten Fall benötigen wir also fünf Vergleiche. Rechnet man das mit dem Zweierlogarithmus nach, kommt man auf 4,32. Das muss man aufrunden auf die nächste Ganzzahl, also fünf. Dass die Zahl fünf stimmt, sieht man auch daran, dass 2 hoch vier gleich 16 ist, also weniger als 20. ### Folie 29 — Gedankenspiel: „20 Questions“ mit binärer Suche [Folie 29 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=29) Ziel bei „20 Questions“: Durch geschickte Ja-NeinFragen ein Objekt oder eine Person erraten, das bzw. die sich jemand anderes ausgedacht hat. Effektive Strategie: mit jeder Frage die noch in Frage kommende Antwortmöglichkeiten halbieren Mit den richtigen 20 Fragen könnte man dann aus einer Menge von mehr als einer Million Möglichkeiten das Gesuchte ermitteln. Um den ersten Buchstaben eines Wortes zu ermitteln (Alphabet: 26 Buchstaben) genügen max. fünf Fragen. Warum? Die übrigen 15 Fragen reichen dann aber evtl. nur noch, um drei weitere Buchstaben zu ermitteln. #### Transkript **[Video 09:34–10:13](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=574)** Es muss also die nächste Zweierpotenz sein. Interessant. Gibt es da vielleicht eine Verbindung zum Spiel Twenty Questions? Du weißt schon, dass wir das nicht mehr in den drei Minuten schaffen, oder? Okay, also gut. Tatsächlich gibt es eine Parallele zwischen der Binärsuche und dem Spiel Twenty Questions. **[Video 10:13–10:27](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=613)** Bei Twenty Questions versucht ein Spieler durch geschicktes Fragen ein vom anderen Spieler gedachtes Objekt oder eine Person zu erraten. Die effektivste Strategie ist es, mit jeder Frage die Menge der möglichen Antworten zu halbieren, genau wie bei der binären Suche. **[Video 10:27–10:59](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=627)** Stimmt. Und mit 20 Fragen kann man ja aus über einer Million verschiedenen Möglichkeiten die richtige Antwort finden. Das bringt mich auf eine Idee. Man könnte doch zum Beispiel fragen, ob der Name des gesuchten Objekts mit einem Buchstaben aus der ersten oder aus der zweiten Hälfte des Alphabets beginnt. Das macht man dann so lange, bis man den ersten Buchstaben hat. Dann fragt man nach den zweiten Buchstaben. Wie weit kommt man jetzt damit? Das ist ein interessanter Ansatz. Lass uns das mal durchrechnen. Das Alphabet hat 26 Buchstaben. Mit jeder Frage halbieren wir den Suchraum. Also brauchen wir maximal fünf Fragen, um den ersten Buchstaben zu bestimmen. **[Video 10:59–11:37](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=659)** Dann bleiben uns also noch fünfzehn Fragen für den Rest. Das reicht, um mindestens drei weitere Buchstaben zu ermitteln. Insgesamt könnten wir also im schlechtesten Fall nur vier Buchstaben des Wortes herausfinden. Ah Mist! Vielleicht werde ich beim nächsten Mal, wenn mir jemand das spielen will, einfach vorschlagen, dass sich mein Gegenspieler nur Wörter mit maximal sechs Buchstaben ausdenken darf. Schau, du bist ja ein ganz schlauer Schlawiner. Aber lass uns das noch mal durchchecken. Ah, okay. Mit den ersten vier Buchstaben kannst du die meisten sechsstelligen Wörter wahrscheinlich tatsächlich erraten. Aber mir kommt eine Idee, wie du noch besser wirst. ### Folie 30 — Optimierung der Strategie [Folie 30 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=30) Ideen: Häufige Buchstabenkombinationen nutzen (z. B. "S-C-H") und nach Anfangsund Endbuchstaben fragen. Hoffnung: z.B. erste zwei Buchstaben "S-C“ →dritte Frage nicht mehr nötig! Weitere Optimierung durch Ausnutzen sprachlicher Eigenheiten. Anfangsbuchstaben "S", "A", "E", "K", "B": 50% aller deutschen Wörter Zuerst nach diesen fragen, um den Suchraum schneller einzugrenzen. #### Transkript **[Video 10:59–11:37](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=659)** Dann kannst du sogar noch längere Wörter mit zwanzig Fragen erraten. **[Video 11:37–12:00](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=697)** Du könntest zum Beispiel ausnutzen, dass es bestimmte Buchstabenkombinationen gibt. Nehmen wir zum Beispiel SCH im Deutschen. Wenn wir wissen, dass die ersten zwei Buchstaben SC sind, können wir die dritte Frage überspringen. Das spart uns eine Frage. Clever. Und wir könnten ja auch von hinten fragen. Eine ausgezeichnete Idee. Wenn wir die ersten zwei oder drei Buchstaben haben, könnten wir nach den letzten Buchstaben fragen. Das erhöht die Wahrscheinlichkeit, das Wort zu erraten. **[Video 12:00–12:36](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=720)** Erheblich. Können wir vielleicht noch mehr optimieren? Bestimmt, oder? Ja, klar. Halte dich fest. Die Verteilung der Anfangsbuchstaben von Wörtern ist ja nicht gleichmäßig. Es gibt viel weniger Wörter, die mit Y beginnen, als mit S. Ich habe kurz nachgeschaut. Im Deutschen machen Wörter, die mit den Buchstaben S, A, E, K und B beginnen, etwa fünfzig Prozent aller Wörter aus. Ah, interessant. Wie könnten wir das denn in unserer Strategie nutzen? Statt das Alphabet einfach zu halbieren, könnten wir zuerst fragen, ob das gesuchte Wort mit einem dieser fünf Anfangsbuchstaben beginnt. Wenn ja, fragen wir, ob der Buchstabe ein S oder A ist und so weiter. **[Video 12:36–13:12](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=756)** Im anderen Fall fragen wir nach einer anderen Gruppe von Buchstaben, die häufig am Anfang vorkommt. So ermitteln wir den ersten Buchstaben vielleicht schon mit drei Fragen statt mit fünf. Mhm, das klingt nach einer echten Optimierung. Ah, das interessiert. ### Folie 31 — Best-Case Komplexität: [Folie 31 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.2-binary-search.pdf#page=31) Prinzip: Teile und Herrsche Ω(1) Wiederholte Halbierung Element wird direct in der Mitte gefunden des Suchbereichs Abbruch bei erfolgloser Suche: Wenn sich Startund Endindex überkreuzen. Voraussetzung: Sortiertes Array Worst-Case Komplexität: O(log n) Praktische Anwendung: Effizient bei großen, sortierten Datensätzen Deutlich besser als O(n) bei linearer Suche > Bildinhalte sind nicht transkribiert; siehe Originalfolie. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 12:36–13:12](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=756)** Das Prinzip erinnert mich auch an was anderes aus der Informatik. Du meinst garantiert den Ansatz, den Informationsgewinn zu maximieren. Das ist ein wichtiges Prinzip, das Sie später in Kursen zum maschinellen Lernen oder Information Retrieval noch genauer kennen lernen werden. Es ist die Basis für Entscheidungsbäume. Faszinierend, wie wir von einem einfachen Spiel zu fortgeschrittenen Informatikkonzepten gekommen sind, oder? **[Video 13:12–13:31](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=792)** So ist die Informatik offen. Man beginnt mit einem alltäglichen Problem und entdeckt dabei grundlegende Prinzipien, die weit über den ursprünglichen Kontext hinausgehen. Wir haben gesehen, wie wichtig es ist, kreativ zu denken und Wissen aus verschiedenen Bereichen zu kombinieren. Oft kann man Probleme viel effizienter lösen, wenn man Domänenwissen hat. Und bevor du jetzt wieder rummeckerst, **[Video 13:31–14:09](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=811)** Domänenwissen ist fachspezifisches Wissen über die Umgebung, in der ein Problem auftritt. Domänenwissen bei der Problemlösung zu berücksichtigen, ist eine nützliche Fähigkeit für angehende Informatikerinnen und Informatiker. Absolut. Ich denke, das reicht für heute. Stimmt. Ha! Jetzt weiß ich, wie ich die Vorlesung mit den Socken hätte beginnen können. Es gibt nämlich eine natürliche Reihenfolge der Farbtöne gemäß der Wellenlänge des Lichts. Stimmt. Aber welches reale Problem löst denn bitte die binäre Suche nach Socken basierend auf Farben? Na, es würde den Studierenden helfen, sich schneller anzuziehen. Vielleicht kämen sie dann pünktlicher zur Vorlesung. Glaubst du wirklich, das ist die Ursache? **[Video 14:09–14:15](https://www.youtube.com/watch?v=vRcepVVlvrQ&t=849)** Dies war Inf-Einf-B.