# 3.1 Lineare Suche Quelle: https://inf.zone/lectures/3-algorithmen/short-3-1-lineare-suche/ ## Video [Video ansehen (1080p)](https://videos.inf.zone/528b1f9018e80bdc/short-3-1-lineare-suche-1080p.mp4) · [Video (720p)](https://videos.inf.zone/528b1f9018e80bdc/short-3-1-lineare-suche-720p.mp4) · [Video (480p)](https://videos.inf.zone/528b1f9018e80bdc/short-3-1-lineare-suche-480p.mp4) · [Video auf YouTube](https://youtu.be/7YXOQ6bm0K8) ## Material - [Folien](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-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 — Lineare Suche [Folie 1 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=1) #### Transkript **[Video 00:00–00:35](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=0)** Dies ist Inf-Einf-B. Heute lineare Suche. Willkommen zu unserer heutigen Vorlesung. Schön, dass du wieder da bist. Ja, finde ich auch. ### Folie 2 [Folie 2 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=2) Die Lineare Suche ist ein einfacher Algorithmus. Die Idee des Algorithmus besteht darin, zur Suche nach einem Element in einem Array das Array von vorne nach hinten zu durchlaufen und jedes Element mit dem gesuchten Wert zu vergleichen. (Ein Algorithmus ist eine schrittweise Anleitung zur Durchführung einer Aufgabe.) #### Transkript **[Video 00:00–00:35](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=0)** Was machen wir heute? Heute beginnen wir mit Algorithmen und zwar der linearen Suche. Das ist ein ganz einfaches Verfahren. Da sind wir schnell fertig. Gut. Hast du noch einen Tipp, wie man Algorithmen am besten versteht? Also wenn du glaubst, dass die Studierenden schon Schwierigkeiten mit der linearen Suche haben, dann. Nein. Ich glaube, die lineare Suche bereitet ihnen überhaupt keine Probleme. Ich meinte ganz allgemein. **[Video 00:35–01:06](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=35)** Also, was den meisten Menschen wohl hilft, wenn es darum geht, Algorithmen zu verstehen, ist sie Schritt für Schritt durchzugehen und dabei den aktuellen Zustand aufzuschreiben. Also, man geht den Algorithmus Zeile für Zeile durch und notiert sich den Inhalt aller Variablen. Man schreibt also jede Codezeile auf und darunter oder darüber die aktuellen Werte. Bei Schleifen kann man die Notizen einrücken, bei Bedingungen kann man mit Pfeilen zeigen, wo es in welchem Fall weitergeht. Stimmt. So lernt man das analytische Denken, das in der Informatik ja so wichtig ist. Aber lass uns jetzt mit der linearen Suche beginnen, bevor wir abschweifen. **[Video 01:06–01:34](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=66)** Heute beschäftigen wir uns also mit der linearen Suche. Dies ist ein grundlegender Algorithmus, den wir verwenden, um ein bestimmtes Element in einem Array zu finden. Ein Algorithmus ist im Wesentlichen eine präzise, schrittweise Anleitung zur Lösung eines Problems oder zur Durchführung einer Aufgabe. Die lineare Suche ist ein besonders einfacher, aber dennoch wichtiger Algorithmus. Er bildet die Grundlage für viele komplexere Suchverfahren und ist oft der erste Algorithmus, den Studierende der Informatik kennenlernen. **[Video 01:34–02:07](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=94)** Stellen Sie sich folgendes Szenario vor: Wir haben ein unsortiertes Array von ganzen Zahlen im Speicher unseres Computers. Unsere Aufgabe ist es nun, nach einem bestimmten Wert in diesem Array zu suchen, um festzustellen, ob er enthalten ist oder nicht. Ein praktisches Beispiel wäre die Überprüfung von Teilnehmernummern bei einer großen Veranstaltung. Stellen Sie sich vor, Sie organisieren eine Konferenz und haben die Registrierungsnummern der angemeldeten Personen in einem Array gespeichert. Wenn nun jemand den Veranstaltungsort betreten möchte, zeigt er einen QR-Code mit der Nummer, und Sie müssen schnell überprüfen, ob die Nummer gültig ist. **[Video 02:07–02:45](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=127)** Also, ob sie im Array aller gültigen Nummern vorkommt. Das ist ein gutes Beispiel. Es zeigt auch, warum die Effizienz bei Suchalgorithmen so wichtig ist. Stellen Sie sich vor, wie mühsam es wäre, nach einer bestimmten Nummer zu suchen, wenn man eine Kiste mit unsortierten Zetteln hätte. Jeder für eine der Nummern. Die Schlange am Einlass, die will ich mir gar nicht erst vorstellen. Kommen wir nun zur Funktionsweise der linearen Suche. Die Idee hinter diesem Algorithmus ist denkbar einfach. ### Folie 3 [Folie 3 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=3) Pseudocode Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript **[Video 02:07–02:45](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=127)** Wir iterieren über das Array von links nach rechts und suchen dabei nach einem bestimmten Element. In Pseudocode lässt sich dies folgendermaßen darstellen: Wiederhole, beginnend beim ersten Element. Wenn das aktuelle Element das Gesuchte ist, stoppe. **[Video 02:45–03:00](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=165)** Andernfalls gehe zum nächsten Element. Dieser Prozess wird so lange fortgesetzt, bis wir entweder das gesuchte Element finden oder das Ende des Arrays erreichen. ### Folie 4 — Beispiel [Folie 4 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=4) 9 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:45–03:00](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=165)** In der Tat sehr einfach. Zeig uns doch mal ein Beispiel. Natürlich. Lassen Sie uns das anhand eines Beispiels veranschaulichen. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** Betrachten wir folgendes Beispiel: Wir haben ein Array mit 15 Elementen und suchen nach dem Wert 9. Die lineare Suche würde wie folgt ablaufen: Wir beginnen mit dem ersten Element, 11. Ist es 9? Nein, also gehen wir weiter. ### Folie 5 — Beispiel [Folie 5 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=5) 9 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** Das nächste Element ist 23. ### Folie 6 — Beispiel [Folie 6 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=6) 9 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** Auch nicht 9, also weiter. ### Folie 7 — Beispiel [Folie 7 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=7) 9 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** 8 ist ebenfalls nicht 9. ### Folie 8 — Beispiel [Folie 8 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=8) 9 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** 14 ist nicht 9. ### Folie 9 — Beispiel [Folie 9 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=9) 9 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** 30 ist nicht 9. ### Folie 10 — Beispiel [Folie 10 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=10) 9 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** Jetzt kommen wir zu 9. ### Folie 11 — Beispiel [Folie 11 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=11) 9 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** Das ist unser Zielwert. ### Folie 12 — Beispiel [Folie 12 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=12) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** Wir können die Suche beenden. ### Folie 13 — Beispiel [Folie 13 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=13) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** Wie Sie sehen, mussten wir in diesem Fall sechs Vergleiche durchführen, um das gesuchte Element zu finden. ### Folie 14 — Beispiel [Folie 14 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=14) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:00–03:33](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=180)** Das Verfahren ist also zwar sehr einfach, aber auch nicht besonders effizient. ### Folie 15 — Beispiel [Folie 15 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=15) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 16 — Beispiel [Folie 16 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=16) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 17 — Beispiel [Folie 17 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=17) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 18 — Beispiel [Folie 18 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=18) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Gut erklärt. ### Folie 19 — Beispiel [Folie 19 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=19) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Vielleicht sollten wir auch noch ansprechen, was passiert, wenn das Element gar nicht im Array enthalten ist. ### Folie 20 — Beispiel [Folie 20 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=20) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Eine ausgezeichnete Frage. ### Folie 21 — Beispiel [Folie 21 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=21) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Lassen Sie uns genau diesen Fall im nächsten Beispiel betrachten. ### Folie 22 — Beispiel [Folie 22 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=22) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** In diesem Beispiel suchen wir nach dem Wert 50 in unserem Array. ### Folie 23 — Beispiel [Folie 23 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=23) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Wie Sie sehen können, ist 50 nicht im Array enthalten. ### Folie 24 — Beispiel [Folie 24 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=24) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Die lineare Suche würde dennoch folgendermaßen ablaufen. ### Folie 25 — Beispiel [Folie 25 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=25) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Wir beginnen wieder beim ersten Element und vergleichen jedes Element der Reihe nach mit 50. ### Folie 26 — Beispiel [Folie 26 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=26) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Da 50 nicht im Array vorhanden ist, müssen wir jeden einzelnen Wert überprüfen. ### Folie 27 — Beispiel [Folie 27 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=27) 50 gesucht: 11 23 8 14 30 9 6 17 22 28 25 15 7 10 19 Wiederhole, beginnend beim ersten Element: Wenn das aktuelle Element das Gesuchte ist, stoppe. Andernfalls gehe zum nächsten Element. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 03:33–04:13](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=213)** Erst nachdem wir das letzte Element, die 19, erreicht und festgestellt haben, dass es nicht 50 ist, können wir mit Sicherheit sagen, dass 50 nicht im Array enthalten ist. ### Folie 28 [Folie 28 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=28) Fälle Worst Case: Gesuchtes Element kommt gar nicht vor. Dann müssen wir alle Elemente prüfen. Best Case: Gesuchtes Element ist das allererste Element. Dann benötigen wir nur einen Vergleich. #### Transkript **[Video 04:13–04:28](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=253)** In diesem Fall mussten wir alle 15 Elemente des Arrays überprüfen. Dies zeigt uns den Worst-Case-Fall der linearen Suche. Wenn das gesuchte Element nicht vorhanden ist oder sich am Ende des Arrays befindet, müssen wir das gesamte Array durchlaufen. Kommen wir nun zur Komplexität der linearen Suche. **[Video 04:28–04:58](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=268)** Die Effizienz eines Algorithmus wird oft durch seine Laufzeitkomplexität ausgedrückt. Im Worst-Case-Szenario, wenn das gesuchte Element das letzte Element des Arrays ist oder gar nicht im Array vorkommt, müssen wir alle n Elemente durchsuchen. Man sagt, die Zeitkomplexität der linearen Suche ist O von n, wobei n die Anzahl der Elemente im Array ist. Der Best-Case tritt ein, wenn das gesuchte Element gleich das erste Element des Arrays ist. In diesem Fall finden wir es sofort und benötigen nur einen einzigen Vergleich. ### Folie 29 [Folie 29 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=29) O(n) Laufzeitkomplexität Ω(1) #### Transkript **[Video 04:28–04:58](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=268)** Dies entspricht einer Komplexität Omega von eins, was bedeutet **[Video 04:58–05:29](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=298)** Dass die Laufzeit konstant und unabhängig von der Größe des Arrays ist. ### Folie 30 — Vor- und Nachteile [Folie 30 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=30) Vorteile: Einfach zu verstehen und zu implementieren Funktioniert mit unsortierten Arrays Nachteile: Ineffizient für große Datenmengen Durchschnittliche Laufzeit wächst linear mit der Arraygröße #### Transkript **[Video 04:58–05:29](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=298)** Mhm, das klingt einleuchtend. Aber was heißt das denn jetzt für die Praxis? Nun, in der Praxis bedeutet das, dass die lineare Suche für kleine Arrays durchaus effizient sein kann. Bei größeren Datenmengen kann es sinnvoll sein, einen effizienteren Algorithmus zu verwenden. Genau. ### Folie 31 [Folie 31 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=31) 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 04:58–05:29](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=298)** Ein Beispiel dafür werden wir uns später noch anschauen. Bevor wir schließen, wie wäre es denn mit unserer Rubrik die drei Extra Minuten? Hast du vielleicht ein interessantes Rätsel griffbereit, das zur linearen Suche passt? **[Video 05:29–06:02](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=329)** Rein zufällig habe ich so etwas griffbereit. Ja. Das klingt spannend. Zeig mal her. ### Folie 32 [Folie 32 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=32) ```c #include #include #define ARRAY_SIZE 10000 bool linear_search(int arr[], int x) { for (int i = 0; i < ARRAY_SIZE; i++) { if (arr[i] == x) return true; } return false; } ``` ```c int main() { int numbers[ARRAY_SIZE]; for (int i = 0; i < 63; i++) { numbers[i] = i + 1; } if (linear_search(numbers, 64)) { printf("gefunden!\n"); } return 0; } ``` #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 33 [Folie 33 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=33) ```text bool linear_search(int arr[], int size, int x) { for (int i = 0; i < size; i++) { if (arr[i] == x) return true; } return false; } // Im Hauptprogramm: if (linear_search(numbers, 63, 64)) { printf("gefunden!\n"); } ``` #### Transkript **[Video 05:29–06:02](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=329)** Hier ist ein Programm, das sich komisch verhält. Hier sehen Sie eine Implementierung der linearen Suche in C. Die Person, die das programmiert hat, erstellt einen Array und füllt die ersten 63 Elemente mit den Zahlen 1 bis 63. Dann wird nach der Zahl 64 gesucht. Überraschenderweise meldet das Programm, dass 64 gefunden wurde. Können Sie erklären, warum das passiert? Das ist in der Tat rätselhaft. Am besten halten Sie hier kurz das Video an, bevor wir das Rätsel dann gleich auflösen. **[Video 06:02–06:37](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=362)** Was könnte hier vor sich gehen? Nun sind alle gespannt. Kannst du uns erklären, was das Problem ist? Nicht das Problem. Es sind gleich mehrere. Erstens: Der Hauptfehler liegt in einer falschen Annahme über die Initialisierung von Arrays in C. Nur die ersten 63 Elemente werden explizit mit Werten belegt. Die restlichen 937 Elemente enthalten folglich undefinierte Werte. [Anm.: Es sind 9937 Elemente: 10000 − 63.] Es ist gut möglich, dass einer dieser undefinierten Werte zufällig 64 ist. Zweitens: Die Funktion linear_search verwendet die globale Konstante ARRAY\_SIZE, um die Schleife zu steuern. Das ist schlechter Stil. ### Folie 34 — Lineare Suche: Element für Element von links nach [Folie 34 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.1-linear-search.pdf#page=34) Array-Größe als Parameter statt global definieren rechts durchgehen Komplexität: O(n) im Worst Case, Unterschied zwischen deklarierter und genutzter Ω(1) im Best Case Array-Größe beachten Einfach zu implementieren, Vorsicht bei nicht-initialisierten aber ineffizient bei großen Arrays in C:Werte sind Datenmengen undefiniert > Bildinhalte sind nicht transkribiert; siehe Originalfolie. #### Transkript **[Video 06:37–07:07](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=397)** Da die Funktion dadurch weniger flexibel ist. Es wäre besser, die Größe als Parameter zu übergeben. Drittens, und das hängt mit den anderen Problemen zusammen, wird beim Suchen nicht zwischen der deklarierten Größe des Arrays und der Anzahl der tatsächlich belegten Elemente unterschieden. Das Array hat ja tausend deklarierte Elemente, aber nur 63 werden initialisiert. [Anm.: Das gezeigte Array hat 10000 deklarierte Elemente.] Die Größe des Arrays spielt für die Suche gar keine Rolle. Viel wichtiger ist die Anzahl der darin verwendeten Elemente. Um diese Probleme zu beheben, könnten wir die Funktion wie folgt umschreiben. Wunderbar. **[Video 07:07–07:29](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=427)** Also, wir merken uns: In C werden Arrays nicht automatisch initialisiert. Anstelle von globalen Variablen sind oft Funktionsparameter sinnvoller. Und wir müssen bei Arrays nicht nur die deklarierte Größe im Blick haben, sondern auch darüber buchführen, wie viele Elemente tatsächlich verwendet werden. Genau. Und denken Sie daran: Lineare Suche, da weiß man, was drin ist. **[Video 07:29–08:05](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=449)** Oder lineare Suche. Ich bin doch nicht blöd. Ja. Und was sagst du zu unserem Puzzle, wo auf einmal 64 im Array war? Vielleicht staunt der Fachmann und der Laie wundert sich. Oh ja, unbedingt. Vielleicht gibt es dazu ja schon bald eine Fortsetzung mit dem Titel „Die Rückkehr der lebenden uninitialisierten Arrays“. Ein echter Schocker für alle, die C lernen. Okay, ich glaube, es reicht. Hast du noch einen letzten Tipp für unsere Studierenden? Natürlich. Vergessen Sie nicht, Coden ist wie Zähneputzen, zweimal täglich für beste Ergebnisse. Auf jeden Fall. Bis zum nächsten Mal. **[Video 08:05–08:10](https://www.youtube.com/watch?v=7YXOQ6bm0K8&t=485)** Dies war Inf-Einf-B.