% Dieses Dokument ist in der Zusammenarbeit von angehenden und % ausgebildeten Informatiklehrkräften entstanden. % Der Herausgeber dieses Dokuments ist die Fachgruppe Informatische % Bildung in NRW der Gesellschaft für Informatik. % % Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0 % https://creativecommons.org/licenses/by-nc-sa/4.0/deed.de % % Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden, % sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben % und auf die ursprünglichen Urheber verwiesen wird. % Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen. % % Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen % Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich. % % Die Sammlung der Dokumente steht unter % https://matsam.fg-ibn.gi.de % zur Verfügung. % % Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht % unter https://www.ctan.org/pkg/schule % zur Verfügung. \chapter{Das neue CD-Regal} \label{cap:regal} \begin{uebersichtBox} Das erste Kapitel frischt Ihr Vorwissen zur linearen Liste, sowie deren Nachteile auf, wenn es um die Suche eines bestimmten Elementes geht. Im Laufe des Kapitels entwickeln Sie eine Methode, die sich von der linearen Suche in einer Liste abgrenzt und sich als wesentlich effektiver erweist. \end{uebersichtBox} \begin{lernzieleBox} Nach der Bearbeitung dieses Kapitels\ldots \begin{smallitemize} \item sind Sie in der Lage, zu benennen, warum sich die lineare Liste nicht zur Verwaltung großer Datenmengen eignet. \item kennen Sie das Prinzip der \enquote{Binären Suche} und können es auf eine Menge von Elementen anwenden. \end{smallitemize} \end{lernzieleBox} \section{Auf der Suche nach Sunrise Avenue} Trotz der Möglichkeit, sich Lieder über Online-Shops direkt herunterzuladen, haben Sie eine große Sammlung von Musik-CDs in einer Schachtel in Ihrem Zimmer stehen. Als Sie eines Tages aus der Schule kommen, strahlt Ihre Mutter Sie an: \enquote{Heute sind die neuen Regale für dein Zimmer gekommen. Ich habe sie direkt mal angebracht und deine CDs eingeräumt. Schau mal, wie's dir gefällt!} In Ihrem Zimmer nehmen Sie die Arbeit Ihrer Mutter in Augenschein -- alle Ihre CDs sind fein säuberlich aufgereiht. Da Ihnen jetzt der Sinn nach etwas Musik steht, entschließen Sie sich, ein Album aus Ihrer Sammlung herauszusuchen und sich danach an die Hausaufgaben zu machen. \begin{center} \begin{tikzpicture} \foreach \artist [count=\yi] in {Unheilig -- Lichter der Stadt, Silbermond -- Himmel auf, Xavier Naidoo -- Danke fürs Zuhören, Santiano -- Bis ans Ende der Welt, Ivy Quainoo -- Ivy, Deichkind -- Befehl von ganz unten, Adele -- 21, Katie Melua -- Secret Symphony, Madonna -- M D N A, Lana Del Rey -- Born to die, Bruce Springsteen -- Wrecking Ball, The Boss Hoss -- Liberty of Action, Kraftclub -- Mit K, The Overtones -- Gambling Man, David Guetta -- Nothing but the Beat, Tim Bendzko -- Wenn Worte meine Sprache wären, Caligola -- Back to Earth, Roxette -- Travelling, Unisonic -- Unisonic, Sunrise Avenue -- Out of Style, Stefanie Heinzmann -- Stefanie Heinzmann, Nickelback -- Here and Now, Coldplay -- Mylo Xyloto, Michel Teló -- Ai Se Eu Te Pego, Die Toten Hosen -- Tage wie dieser, Luxuslärm -- Carousel, Mike Candys -- Smile, Rihanna -- Talk That Talk, Eisblume -- Ewig, Rea Garvey -- Can't Stand The Silence, Culcha Candela -- Flätrate, Ed Sheeran -- +, Boy -- Mutual Friends, Kings of Leon -- Only By The Night, Alpa Gun -- Ehrensache, Alabama Shakes -- Boys \& Girls, Gotye -- Making Mirrors, One Direction -- Up all Night, Rizzle Kicks -- Stereo Typical, Katy Perry -- Teenage Dream, The Black Keys -- El Camino, Lostprophets -- Weapons, Script -- Science \& Faith, Alan Jackson -- Good Time, AC/DC -- Back in Black, Green Day -- American Idiot, Linkin Park -- A Thousand Suns, die ärzte -- auch, Fall Out Boy -- Folie à Deux, Flogging Molly -- Speed of Darkness} { \draw[rotate=90,fill=gray!10] (0,\yi*0.3) rectangle node[rotate=90]{\tiny\artist} (5,\yi*0.3+0.3); } \end{tikzpicture} \end{center} \begin{aufgabe} \begin{teilaufgaben} \teilaufgabe Suchen Sie das Album von Sunrise Avenue aus Ihrer CD-Sammlung oben heraus. Notieren Sie dabei, wie viele CDs Sie sich angesehen haben, bis Sie das Album gefunden haben. \teilaufgabe Suche Sie nun das Album von Linkin Park aus der CD-Sammlung heraus. Notieren Sie sich auch hier, wie viele CDs Sie sich angesehen haben. \teilaufgabe Beschreiben Sie, welchen Zusammenhang Sie zu einer Ihnen bekannten Datenstruktur sehen. Welche Nachteile ergeben sich bei der Suche nach einer bestimmten CD? Und was bedeutet dies für den Fall, dass Sie nach einer CD suchen, die gar nicht im Regal steht? \teilaufgabe Sehen Sie Möglichkeiten, die Suche zu beschleunigen? \end{teilaufgaben} \end{aufgabe} \begin{loesung} \begin{teilaufgaben} \teilaufgabeOhneLoesung \teilaufgabeOhneLoesung \teilaufgabe Das CD-Regal lässt sich durch eine lineare Liste repräsentieren. Da die CDs keinerlei Ordnung unterliegen, muss jede CD einzeln betrachtet werden, um ein bestimmtes Album zu finden. Um festzustellen, dass eine CD nicht vorhanden ist, muss also immer die komplette Liste durchlaufen werden -- in diesem Fall sind es 50 Einträge. \teilaufgabe Eine Möglichkeit, die Suche zu beschleunigen, besteht darin, die CDs in irgendeiner sinnvollen Weise zu sortieren, beispielsweise nach Interpreten oder Albumnamen. \end{teilaufgaben} \end{loesung} \section{Geht das auch einfacher?} Einen arbeitsreichen Nachmittag später haben Sie die CDs in eine neue Reihenfolge gebracht: sie sind jetzt nach den Namen der Interpreten aufsteigend sortiert. \begin{aufgabe} \begin{teilaufgaben} \teilaufgabe Suchen Sie nun erneut die CD von Sunrise Avenue aus Ihrer unten stehenden Sammlung heraus und notieren Sie sich wiederum die Anzahl der CDs, die Sie sich ansehen mussten. Verfahren Sie ebenso mit dem Album von Linkin Park, sowie mit dem Album von Michael Jackson. \teilaufgabe Tauschen Sie sich anschließend mit einem Partner darüber aus, wie Sie bei der Suche vorgegangen sind. Lässt sich diese Vorgehensweise verallgemeinern? \end{teilaufgaben} \end{aufgabe} \begin{loesung} Da jeder Mensch bei der Suche ein wenig anders vorgehen wird, lässt sich an dieser Stelle nur eine allgemeine Aussagen treffen. Dadurch, dass die CDs sortiert sind, bietet sich ein enormer Vorteil. So kann die Suche allein dadurch beschleunigt werden, dass man intuitiv abschätzt, an welcher Stelle etwa ein Buchstabe liegen könnte und sich anschließend nur die Alben im näheren Umfeld ansieht. Durch die Sortierung wird gleichzeitig eine \enquote{Richtung} vorgegeben, in die man die Suche fortsetzen muss. Sucht man beispielsweise eine CD vom Interpreten Luxuslärm und beginnt seine Suche beim Buchstaben \enquote{O}, so ist klar, dass die Suche im linken Teil der Liste weitergehen muss. Um festzustellen, dass ein Album nicht im Regal vorhanden ist, genügt es, sich die Alben anzusehen, die denselben Anfangsbuchstaben haben -- somit kann auch für diesen Fall die Anzahl der Suchvorgänge erheblich reduziert werden. \end{loesung} \begin{center} \begin{tikzpicture} \foreach \artist [count=\yi] in {Xavier Naidoo -- Danke fürs Zuhören, Unisonic -- Unisonic, Unheilig -- Lichter der Stadt, Tim Bendzko -- Wenn Worte meine Sprache wären, The Overtones -- Gambling Man, The Boss Hoss -- Liberty of Action, The Black Keys -- El Camino, Sunrise Avenue -- Out of Style, Stefanie Heinzmann -- Stefanie Heinzmann, Silbermond -- Himmel auf, Script -- Science \& Faith, Santiano -- Bis ans Ende der Welt, Roxette -- Travelling, Rizzle Kicks -- Stereo Typical, Rihanna -- Talk That Talk, Rea Garvey -- Can't Stand The Silence, One Direction -- Up all Night, Nickelback -- Here and Now, Mike Candys -- Smile, Michel Teló -- Ai Se Eu Te Pego, Madonna -- M D N A, Luxuslärm -- Carousel, Lostprophets -- Weapons, Linkin Park -- A Thousand Suns, Lana Del Rey -- Born to die, Kraftclub -- Mit K, Kings of Leon -- Only By The Night, Katy Perry -- Teenage Dream, Katie Melua -- Secret Symphony, Ivy Quainoo -- Ivy, Green Day -- American Idiot, Gotye -- Making Mirrors, Flogging Molly -- Speed of Darkness, Fall Out Boy -- Folie à Deux, Eisblume -- Ewig, Ed Sheeran -- +, Die Ärzte -- auch, Die Toten Hosen -- Tage wie dieser, Deichkind -- Befehl von ganz unten, David Guetta -- Nothing but the Beat, Culcha Candela -- Flätrate, Coldplay -- Mylo Xyloto, Caligola -- Back to Earth, Bruce Springsteen -- Wrecking Ball, Boy -- Mutual Friends, Alpa Gun -- Ehrensache, Alan Jackson -- Good Time, Alabama Shakes -- Boys \& Girls, Adele -- 21, AC/DC -- Back in Black} { \draw[rotate=90,fill=gray!10] (0,\yi*0.3) rectangle node[rotate=90]{\tiny\artist} (5,\yi*0.3+0.3); } \end{tikzpicture} \end{center} \section{Die binäre Suche} Eine Möglichkeit, sich die Suche in einer sortierten Menge zu vereinfachen, besteht in der sogenannten \emph{binären Suche}. Die Grundidee liegt darin, mit jedem Suchschritt die Anzahl der möglichen Elemente zu verkleinern und sich so insgesamt nur wenige Elemente anschauen zu müssen. Als Menschen haben wir einen Vorteil gegenüber dem Informatiksystem, wenn es darum geht, nach bestimmten Elementen zu suchen. Vor allem bei einer noch einigermaßen übersichtlichen Menge von Daten, wie den $50$\,CDs, können wir uns häufig auf Erfahrungswerte berufen: Wenn wir beispielsweise nach einem Interpreten mit dem Anfangsbuchstaben \textbf{M} suchen und bei unserer Suche beim Buchstaben N ankommen, werden wir direkt in der unmittelbaren Umgebung dieses Buchstabens suchen. Problematisch wird diese Methode jedoch, wenn es sich statt $50$ um beispielsweise $10.000$\,CDs handelt. Denn in diesem Fall können zwischen zwei Anfangsbuchstaben leicht $400$\,CDs liegen. Also braucht man eine festgelegte Vorgehensweise, die allgemeingültig ist und mit jedem Suchschritt möglichst viele CDs ausschließt. \begin{aufgabe} \begin{teilaufgaben} \teilaufgabe Überlegen Sie sich eine Methode, wie man mit jedem Suchschritt eine gewisse Anzahl an CDs direkt ausschließen kann. \textbf{Tipp:} Beginnen Sie Ihre Suche in der Mitte des Regals. Wie viele CDs können Sie so direkt nach dem ersten Vergleich ausschließen? \teilaufgabe Wenden Sie diese Methode anschließend auf das Regal an und suchen Sie zwei CDs heraus. Notieren Sie die Anzahl der CDs, die Sie dabei betrachten mussten und vergleichen Sie diese mit der Anzahl der benötigten Versuche in den vorherigen Durchgängen. \end{teilaufgaben} \end{aufgabe} \begin{loesung} Umgangssprachlich lässt sich die Suche folgendermaßen formulieren: \begin{itemize} \item Betrachte das mittlere Element! \item Ist es das gesuchte Element? \begin{description} \item[JA] Gib das Element aus und beende die Suche \item[NEIN] Liegt das gesuchte Element links oder rechts vom aktuellen Element? \begin{description} \item[LINKS] Springe zur Hälfte der linken Teilliste und beginne dort von vorne \item[RECHTS] Springe zur Hälfte der rechten Teilliste und beginne dort von vorne \end{description} \end{description} \end{itemize} Sollte der Fall eintreten, dass die verbleibende Liste nicht mehr halbiert werden kann, so ist das gesuchte Album nicht darin enthalten. Wir verdeutlichen uns den Ablauf an einem Beispiel. Zum besseren Verständnis sind die einzelnen Alben im nachfolgenden Bild nummeriert worden. Wir suchen nach dem Album von Coldplay. \begin{enumerate}[label=\bfseries{Schritt ~\arabic*:}, left= 0pt] \item Damit wir die Mitte erhalten addieren wir immer die Nummer der ersten CD mit der letzten und teilen dieses durch zwei. Wenn nötig runden wir ab, da dieses für den Computer einfacher ist. Bei $50$\,CDs berechnen wir das mittlere Element durch $\frac{1 + 50}{2}=25,5 \approx 25$. \hspace{-0.7cm} \begin{tikzpicture}[scale=.95] \foreach \artist [count=\yi] in {50 -- Xavier Naidoo -- Danke fürs Zuhören, 49 -- Unisonic -- Unisonic, 48 -- Unheilig -- Lichter der Stadt, 47 -- Tim Bendzko -- Wenn Worte meine Sprache wären, 46 -- The Overtones -- Gambling Man, 45 -- The Boss Hoss -- Liberty of Action, 44 -- The Black Keys -- El Camino, 43 -- Sunrise Avenue -- Out of Style, 42 -- Stefanie Heinzmann -- Stefanie Heinzmann, 41 -- Silbermond -- Himmel auf, 40 -- Script -- Science \& Faith, 39 -- Santiano -- Bis ans Ende der Welt, 38 -- Roxette -- Travelling, 37 -- Rizzle Kicks -- Stereo Typical, 36 -- Rihanna -- Talk That Talk, 35 -- Rea Garvey -- Can't Stand The Silence, 34 -- One Direction -- Up all Night, 33 -- Nickelback -- Here and Now, 32 -- Mike Candys -- Smile, 31 -- Michel Teló -- Ai Se Eu Te Pego, 30 -- Madonna -- M D N A, 29 -- Luxuslärm -- Carousel, 28 -- Lostprophets -- Weapons, 27 -- Linkin Park -- A Thousand Suns, 26 -- Lana Del Rey -- Born to die, 25 -- Kraftclub -- Mit K, 24 -- Kings of Leon -- Only By The Night, 23 -- Katy Perry -- Teenage Dream, 22 -- Katie Melua -- Secret Symphony, 21 -- Ivy Quainoo -- Ivy, 20 -- Green Day -- American Idiot, 19 -- Gotye -- Making Mirrors, 18 -- Flogging Molly -- Speed of Darkness, 17 -- Fall Out Boy -- Folie à Deux, 16 -- Eisblume -- Ewig, 15 -- Ed Sheeran -- +, 14 -- Die Ärzte -- auch, 13 -- Die Toten Hosen -- Tage wie dieser, 12 -- Deichkind -- Befehl von ganz unten, 11 -- David Guetta -- Nothing but the Beat, 10 -- Culcha Candela -- Flätrate, 9 -- Coldplay -- Mylo Xyloto, 8 -- Caligola -- Back to Earth, 7 -- Bruce Springsteen -- Wrecking Ball, 6 -- Boy -- Mutual Friends, 5 -- Alpa Gun -- Ehrensache, 4 -- Alan Jackson -- Good Time, 3 -- Alabama Shakes -- Boys \& Girls, 2 -- Adele -- 21, 1 -- AC/DC -- Back in Black} { \draw[rotate=90,fill=gray!10] (0,\yi*0.3) rectangle node[rotate=90]{\tiny\artist} (5.5,\yi*0.3+0.3); } \end{tikzpicture} Beim Interpreten von Album 25 handelt es sich um Kraftclub. Unser gesuchtes Album liegt also in der linken Hälfte der Liste, alle Elemente rechts der Mitte und die Mitte selbst brauchen wir nicht mehr weiter zu betrachten. \item Schon nach dem ersten Schritt hat sich Anzahl der Elemente beträchtlich verkleinert. Da wir nun noch über 24 Elemente verfügen, betrachten wir jetzt Element 12 -- Deichkind, da $\frac{1+24}{2} = 12,5 \approx 12$ gilt. \begin{center} \begin{tikzpicture}[scale=.95] \foreach \artist [count=\yi] in {24 -- Kings of Leon -- Only By The Night, 23 -- Katy Perry -- Teenage Dream, 22 -- Katie Melua -- Secret Symphony, 21 -- Ivy Quainoo -- Ivy, 20 -- Green Day -- American Idiot, 19 -- Gotye -- Making Mirrors, 18 -- Flogging Molly -- Speed of Darkness, 17 -- Fall Out Boy -- Folie à Deux, 16 -- Eisblume -- Ewig, 15 -- Ed Sheeran -- +, 14 -- Die Ärzte -- auch, 13 -- Die Toten Hosen -- Tage wie dieser, 12 -- Deichkind -- Befehl von ganz unten, 11 -- David Guetta -- Nothing but the Beat, 10 -- Culcha Candela -- Flätrate, 9 -- Coldplay -- Mylo Xyloto, 8 -- Caligola -- Back to Earth, 7 -- Bruce Springsteen -- Wrecking Ball, 6 -- Boy -- Mutual Friends, 5 -- Alpa Gun -- Ehrensache, 4 -- Alan Jackson -- Good Time, 3 -- Alabama Shakes -- Boys \& Girls, 2 -- Adele -- 21, 1 -- AC/DC -- Back in Black} { \draw[rotate=90,fill=gray!10] (0,\yi*0.3) rectangle node[rotate=90]{\tiny\artist} (5.5,\yi*0.3+0.3); } \end{tikzpicture} \end{center} Das Album ist wieder nicht das gesuchte, es verrät uns aber, dass unser Element wiederum in der linken Teilliste liegen muss. \item Wir wiederholen das bekannte Verfahren für die restlichen Elemente von 1 bis 11. Wir erhalten so $\frac{1 + 11}{2}= $. Das mittlere Element ist in diesem Fall: \enquote{Boy}. Unsere CD liegt demnach in der rechten Hälfte. \begin{center} \begin{tikzpicture}[scale=.95] \foreach \artist [count=\yi] in {11 -- David Guetta -- Nothing but the Beat, 10 -- Culcha Candela -- Flätrate, 9 -- Coldplay -- Mylo Xyloto, 8 -- Caligola -- Back to Earth, 7 -- Bruce Springsteen -- Wrecking Ball, 6 -- Boy -- Mutual Friends, 5 -- Alpa Gun -- Ehrensache, 4 -- Alan Jackson -- Good Time, 3 -- Alabama Shakes -- Boys \& Girls, 2 -- Adele -- 21, 1 -- AC/DC -- Back in Black} { \draw[rotate=90,fill=gray!10] (0,\yi*0.3) rectangle node[rotate=90]{\tiny\artist} (5.5,\yi*0.3+0.3); } \end{tikzpicture} \end{center} \item Betrachten wir nun erneut das mittlere Element der verbleibenden Liste $\frac{7+11}{2} = 9$. Dieses ist das gesuchte. So zeigt sich, dass wir unser Element nach lediglich 4 Schritten gefunden haben. \begin{center} \begin{tikzpicture}[scale=.95] \foreach \artist [count=\yi] in {11 -- David Guetta -- Nothing but the Beat, 10 -- Culcha Candela -- Flätrate, 9 -- Coldplay -- Mylo Xyloto, 8 -- Caligola -- Back to Earth, 7 -- Bruce Springsteen -- Wrecking Ball} { \draw[rotate=90,fill=gray!10] (0,\yi*0.3) rectangle node[rotate=90]{\tiny\artist} (5.5,\yi*0.3+0.3); } \end{tikzpicture} \end{center} \end{enumerate} \end{loesung} \begin{nothelferBox} Betrachten Sie nach jedem Vergleich immer nur noch die Hälfte der CDs und überlegen Sie, ob Sie die linke oder rechte Hälfte betrachten müssen. \end{nothelferBox} Das so entstandene Verfahren nennt man die binäre Suche. Binär leitet sich dabei vom lateinischen \emph{binarius} ab und bedeutet so viel wie \enquote{zweiteilig}. Der Name erklärt sich daher, dass sich bei jedem Suchschritt die Anzahl der zu betrachtenden Elemente halbiert. Dies ist ein enormer Fortschritt gegenüber der ersten Version unser linearen Suche. Im nächsten Kapitel werden Sie sehen, wie man aus der Erkenntnis der binären Suche eine neue Datenstruktur entwickeln kann, die schon durch ihren Aufbau die Suche nach bestimmten Elementen unterstützt. \newpage \begin{lernkontrolleBox} \begin{kontrollaufgabe} Worin liegen Nachteile der Suche in einer linearen Liste? \begin{mcumgebung}(1) \choice[\mcrichtig] Die Suche kann bei einer großen Anzahl von Elementen sehr lange dauern. \choice Die Elemente müssen vor dem Durchlaufen sortiert werden. \choice[\mcrichtig] Es müssen immer alle Elemente von Anfang an durchlaufen werden, auch wenn das letzte Element gesucht wird. \end{mcumgebung} \end{kontrollaufgabe} \begin{kontrollloesung} \mcloesung \end{kontrollloesung} \begin{kontrollaufgabe} Die binäre Suche funktioniert in jeder beliebigen Liste von Elementen. \begin{mcumgebung}(1) \choice Richtig \choice[\mcrichtig] Falsch \end{mcumgebung} \end{kontrollaufgabe} \begin{kontrollloesung} \mcloesung Die Elemente müssen einer Ordnung unterliegen und sortierbar sein. \end{kontrollloesung} \begin{kontrollaufgabe} Wenden Sie die binäre Suche auf die folgende Menge an, um das Element \enquote{Frankreich} zu finden. Markieren Sie dabei alle Elemente, die Sie während Ihrer Suche betrachtet haben. \\[.2cm] \begin{tiny} \begin{tabular}{|l|l|} \hline 1 & Afghanistan\\\hline 2 & Ägypten\\\hline 3 & Albanien\\\hline 4 & Algerien\\\hline 5 & Andorra\\\hline 6 & Angola\\\hline 7 & Antigua und Barbuda\\\hline 8 & Äquatorialguinea\\\hline 9 & Argentinien\\\hline 10 & Armenien\\\hline 11 & Aserbaidschan\\\hline 12 & Äthiopien\\\hline 13 & Australien\\\hline 14 & Bahamas\\\hline 15 & Bahrain\\\hline 16 & Bangladesh\\\hline 17 & Barbados\\\hline 18 & Belgien\\\hline 19 & Belize\\\hline 20 & Benin\\\hline 21 & Bhutan\\\hline 22 & Bolivien\\\hline 23 & Bosnien-Herzegowina\\\hline 24 & Botswana\\\hline 25 & Brasilien\\\hline 26 & Brunei\\\hline 27 & Bulgarien\\\hline 28 & Burkina-Faso\\\hline 29 & Burundi\\\hline 30 & Chile\\\hline 31 & China\\\hline 32 & Costa Rica\\\hline 33 & Côte d'Ivoire\\\hline 34 & Dänemark\\\hline 35 & Deutschland\\\hline 36 & Dominica\\\hline 37 & Dominikanische Republik\\\hline 38 & Ecuador\\\hline 39 & El Salvador\\\hline 40 & Eritrea\\\hline 41 & Estland\\\hline 42 & Fidschi\\\hline 43 & Finnland\\\hline 44 & Frankreich\\\hline 45 & Gabun\\\hline 46 & Gambia\\\hline 47 & Georgien\\\hline 48 & Ghana\\\hline 49 & Grenada\\\hline 50 & Griechenland\\\hline \end{tabular} \begin{tabular}{|l|l|} \hline 51 & Großbritannien\\\hline 52 & Guatemala\\\hline 53 & Guinea\\\hline 54 & Guinea-Bissau\\\hline 55 & Guyana\\\hline 56 & Haiti\\\hline 57 & Honduras\\\hline 58 & Indien\\\hline 59 & Indonesien\\\hline 60 & Irak\\\hline 61 & Iran\\\hline 62 & Irland\\\hline 63 & Island\\\hline 64 & Israel\\\hline 65 & Italien\\\hline 66 & Jamaika\\\hline 67 & Japan\\\hline 68 & Jemen\\\hline 69 & Jordanien\\\hline 70 & Jugoslawien\\\hline 71 & Kambodscha\\\hline 72 & Kamerun\\\hline 73 & Kanada\\\hline 74 & Kap Verde\\\hline 75 & Kasachstan\\\hline 76 & Katar\\\hline 77 & Kenia\\\hline 78 & Kirgisistan\\\hline 79 & Kiribati\\\hline 80 & Kolombien\\\hline 81 & Komoren\\\hline 82 & Kongo, Republik\\\hline 83 & Kroatien\\\hline 84 & Kuba\\\hline 85 & Kuwait\\\hline 86 & Laos\\\hline 87 & Lesotho\\\hline 88 & Lettland\\\hline 89 & Libanon\\\hline 90 & Liberia\\\hline 91 & Libyen\\\hline 92 & Liechtenstein\\\hline 93 & Litauen\\\hline 94 & Luxemburg\\\hline 95 & Madagaskar\\\hline 96 & Makedonien\\\hline 97 & Malawi\\\hline 98 & Malaysia\\\hline 99 & Malediven\\\hline 100 & Mali\\\hline \end{tabular} \begin{tabular}{|l|l|} \hline 101 & Malta\\\hline 102 & Marokko\\\hline 103 & Marshallinseln\\\hline 104 & Mauritanien\\\hline 105 & Mauritius\\\hline 106 & Mexiko\\\hline 107 & Mikronesien\\\hline 108 & Moldawien\\\hline 109 & Monaco\\\hline 110 & Mongolei\\\hline 111 & Mosambik\\\hline 112 & Myanmar\\\hline 113 & Namibia\\\hline 114 & Nauru\\\hline 115 & Nepal\\\hline 116 & Neuseeland\\\hline 117 & Nicaragua\\\hline 118 & Niederlande\\\hline 119 & Niger\\\hline 120 & Nigeria\\\hline 121 & Nordkorea\\\hline 122 & Norwegen\\\hline 123 & Oman\\\hline 124 & Österreich\\\hline 125 & Pakistan\\\hline 126 & Palau-Inseln\\\hline 127 & Panama\\\hline 128 & Papua-Neuguinea\\\hline 129 & Paraguay\\\hline 130 & Peru\\\hline 131 & Philippinen\\\hline 132 & Polen\\\hline 133 & Portugal\\\hline 134 & Ruanda\\\hline 135 & Rumänien\\\hline 136 & Russland\\\hline 137 & Saint Kitts-Nevis\\\hline 138 & Saint Lucia\\\hline 139 & Saint Vincent und Grenadinen\\\hline 140 & Sambia\\\hline 141 & San Marino\\\hline 142 & Sao Tomé und Príncipe\\\hline 143 & Saudi-Arabien\\\hline 144 & Schweden\\\hline 145 & Schweiz\\\hline 146 & Senegal\\\hline 147 & Seychellen\\\hline 148 & Sierra Leone\\\hline 149 & Simbabwe\\\hline 150 & Singapur\\\hline \end{tabular} \begin{tabular}{|l|l|} \hline 151 & Slowakische Republik\\\hline 152 & Slowenien\\\hline 153 & Solomonen\\\hline 154 & Somalia\\\hline 155 & Spanien\\\hline 156 & Sri Lanka\\\hline 157 & Südafrika\\\hline 158 & Sudan\\\hline 159 & Südkorea\\\hline 160 & Surinam\\\hline 161 & Swasiland\\\hline 162 & Syrien\\\hline 163 & Tadschikistan\\\hline 164 & Taiwan\\\hline 165 & Tansania\\\hline 166 & Thailand\\\hline 167 & Togo\\\hline 168 & Tonga\\\hline 169 & Trinidad und Tobago\\\hline 170 & Tschad\\\hline 171 & Tschechische Republik\\\hline 172 & Tunesien\\\hline 173 & Türkei\\\hline 174 & Turkmenistan\\\hline 175 & Tuvalu\\\hline 176 & Uganda\\\hline 177 & Ukraine\\\hline 178 & Ungarn\\\hline 179 & Uruguay\\\hline 180 & Usbekistan\\\hline 181 & Vanuatu\\\hline 182 & Vatikanstadt\\\hline 183 & Venezuela\\\hline 184 & Vereinigte Arabische Emirate\\\hline 185 & Vereinigte Staaten von Amerika\\\hline 186 & Vietnam\\\hline 187 & Weißrußland\\\hline 188 & Westsahara\\\hline 189 & Westsamoa\\\hline 190 & Zaire\\\hline 191 & Zentralafrikanische Republik\\\hline 192 & Zypern\\\hline \end{tabular} \end{tiny} \end{kontrollaufgabe} \begin{kontrollloesung} Reihenfolge der besuchten Elemente: \begin{itemize} \item Wir beginnen die Suche bei Element $\frac{1+192}2=96,5 \approx 96$, Makedonien. Das gesuchte Element befindet sich also unterhalb von Element 96. \item Es verbleiben nun noch 95 Elemente, da Makedonien ebenfalls ausgeschlossen werden kann. Die Mitte ergibt sich also als $\frac{1 + 95}{2}=48\approx 48$, Ghana. Wiederum kein Treffer, es verbleiben 47 Elemente. \item Die neue Mitte ergibt sich als $\frac{1+47}{2}= 24$, Botswana. Das gesuchte Element liegt oberhalb von Element 24. Wir betrachten jetzt nur noch die Elemente von 25 bis 47, da alle anderen bereits ausgeschlossen wurden. \item Wir betrachten noch 23 Elemente, also bestimmen wird die Mitte: $\frac{25 + 47}{2}=36$, Dominica. Dieses ist ebenfalls nicht das gesuchte Element ist. Demnach betrachten wir noch die Elemente 37 bis 47. \item Erneutes Berechnen des mittleren Elementes liefert $\frac{37+47}{2}=42$, und somit Fidschi. Es verbleiben die Elemente 43 bis 47. \item Die Mitte berechnet sich als $\frac{43+47}{2}=45$, also Gabun. Wir betrachten noch die Elemente 43 bis 44. \item Die Mitte berechnet sich für diese Elemente als $\frac{43+44}{2} =43,5 \approx 43$, Finnland. Es verbleibt danach also nur das Element 44. \item Das Element 44 ist Frankreich und damit das Gesuchte. \end{itemize} Die Suche endet damit nach insgesamt 8 betrachteten Elementen. \end{kontrollloesung} \end{lernkontrolleBox} \newpage \begin{loesungenBox} \end{loesungenBox} \printsolutionstype[chapter=\thechapter]{aufgabe} \paragraph{Lernkontrolle}$~$\\ \printsolutionstype[chapter=\thechapter]{kontrollaufgabe}