====== Suchen und Sortieren ======

Weiter zu [[gf_informatik:suchen_und_sortieren:binaersuche|Binäre Suche]]

Direkt zu [[gf_informatik:suchen_und_sortieren:sortieren|Sortieren]]

++++Lernziele lineare und binäre Suche:|
   * Ich kann erklären, wie die lineare Suche und wie die binäre Suche funktioniert.
   * Ich kann die beiden Such-Algorithmen (linear und binär) miteinander vergleichen, d.h. Unterschiede, Vor- und Nachteile/Voraussetzungen erklären. 
   * Ich kann für eine gegebene Anzahl Einträge (Listen-Länge) die maximale Anzahl Abfragen für beide Such-Algorithmen berechnen.
   * Ich kann eine Funktion ''linear\_search(list, value)'' definieren, die nach der linearen Suche die **Position** von ''value'' in ''list'' zurückgibt. 
   * Ich kann eine Funktion ''binary\_search(list, value)'' definieren, die nach der binären Suche die **Position** von ''value'' in ''list'' zurückgibt.
   * Ich kann Suchfunktionen (linear und binär) verwenden, um in mehreren zusammenpassenden Listen zusammengehörende Elemente zu finden – Beispiel: Ausgehend vom Namen über dessen Index in der Namensliste die entsprechende Nummer aus der Nummernliste ermitteln.
++++


==== Einführung ====

Das Ziel einer Suche ist es, in einer grossen Datenmenge möglichst schnell das gesuchte Element zu finden. Beispielsweise suchen wir in einem Lexikon oder Wörterbuch den Eintrag zu einem Begriff, im Telefonbuch die Nummer einer Person oder eines Geschäfts. Heutzutage suchen wir zumeist im Internet - aber wie schafft es [[https://dict.leo.org/englisch-deutsch/search|dict.leo.org]] einen Suchbegriff innert Millisekunden zu finden? Wie findet [[https://tel.search.ch/kantonsschule%20romanshorn|tel.search.ch]] den richtigen Eintrag?

==== Lineare Suche ====
<blockquote>
Gäb si mir wenigschtens d Vorwahl\\ 
Per favore\\ 
De gäbs nume no zäh Millione Kombinatione, ja\\
079 het si gseit\\ 
„Du weisch immer no nüt“, het si gseit\\
Nidmau tschüss het si gseit, ey\\
Und i frage si ob ig ihri - tüt tüt tüt het si gseit, tüt tüt
<cite>[[https://www.youtube.com/watch?v=C8Xv7MKigYo|079 by Lo & Leduc]]</cite>
</blockquote>

Der Sänger von _079_ will die Telefonnummer der Angebeteten unter allen möglichen Schweizer Mobilfunknummern (10-stellig) mit dem Präfix `079` herausfinden. Dafür probiert er sämtliche Nummern von `079 000 00 00` bis `079 999 99 99` durch, was natürlich ziemlich lange dauert...

#### Aufgabe A1 - 079

**Tipp**: Höre oder lese den Liedtext genau ([[https://www.songtexte.com/songtext/lo-and-leduc/079-g5bed3b18.html|Original]], [[https://www.swr3.de/musik/poplexikon/lyrics/lo--leduc-079--songtext-deutsche-bersetzung--lyrics-100.html|Hochdeutsch]], [[https://www.youtube.com/watch?v=C8Xv7MKigYo|Youtube]])!

1. Wie viele Telefonnummern muss der Sänger von _079_ durchprobieren?
1. Wie lange dauert das Probieren einer Telefonnummer?
1. Wie lange dauert die Suche nach der richtigen Nummer bei _079_?
1. Wieso dauert es so lange? Was ist die Rechnung, die hinter der genannten Dauer steckt?
1. Wie lange dauerte die Suche, wenn wir nicht einmal die Vorwahl kennen würden (aber wüssten, dass alle Nummern mit `0` beginnen)?

<nodisp 1>
++++Lösung|

1. 10 Mio - <q>De gäbs nume no zäh Millione Kombinatione, ja</q> \\ 
1. 20 Sekunden - <q>U weni nächär pro Minute drü vo de Nummere usprobier</q> \\ 
1. 6.5 Jahre - <q>De chönnts maximal nume sächsehalb Jahr lang ga</q> \\ 
1. $\frac{10\,000\,000}{365\frac{d}{y} \cdot 24\frac{h}{d} \cdot 60\frac{m}{h} \cdot \frac{3}{m}} \approx 6.342y$
1. Wir hätten nochmals zwei Dezimalstellen, also 100 Mal mehr Möglichkeiten, damit 634 Jahre.

++++
</nodisp>

=== Algorithmus ===
Der einfachste Such-Algorithmus probiert alle Telefonnummern von der kleinsten zur grössten durch. Die Zeit für die Suche steigt **proportional** mit der Anzahl möglichen Nummern an - wir sagen auch, dass die Zeit **linear** mit der Grösse des Suchbereichs wächst, und sprechen von **Linearer Suche**.

Würden wir statt _079_ nicht einmal die Vorwahl kennen, wäre die Suche nochmals zwei Dezimalstellen länger (wenn alle Telefonnummern mit 0 beginnen). Wir müssten also statt 6.5 sogar über 600 Jahre suchen.

{{:gf_informatik:linear_search.png?nolink&400| }}


=== Aufgabe A2: Lineare Suche in Python ===

Betrachte folgenden Datensatz mit Namen und Telefonnummern. Wir haben zwei parallele Listen, die erste mit Namen, die zweite mit den dazugehörigen Telefonnummern. Am gleichen Index ist in der ersten Liste der Name, in der zweiten die Telefonnummer gespeichert.

Zum Beispiel finden wir für den Index `1` Anela in `names[1]` und ihre Nummer 0790000001 in `numbers[1]`.

<bottom-exercise showsolution id="a2" timeout="180">
<template data-type="starter">
names = ['Aja', 'Anela', 'Arwen', 'Isra',
         'Juno', 'Kaida', 'Loelia', 'Luna',
         'Lumiel', 'Lyanna', 'Meyra', 'Miriel',
         'Narcissa', 'Nisha', 'Runa', 'Yuna']
numbers = ['0790000000', '0790000001', '0790000002', '0790000003',
           '0790000004', '0790000005', '0790000006', '0790000007',
           '0790000008', '0790000009', '0790000010', '0790000011',
           '0790000012', '0790000013', '0790000014', '0790000015']
</template>
<template data-type="test">
assert linear_search(names, 'Lyanna') == 9
assert linear_search([1, 2, 3], 3) == 2
</template>
<template data-type="solution">
names = ['Aja', 'Anela', 'Arwen', 'Isra',
         'Juno', 'Kaida', 'Loelia', 'Luna',
         'Lumiel', 'Lyanna', 'Meyra', 'Miriel',
         'Narcissa', 'Nisha', 'Runa', 'Yuna']
numbers = ['0790000000', '0790000001', '0790000002', '0790000003',
           '0790000004', '0790000005', '0790000006', '0790000007',
           '0790000008', '0790000009', '0790000010', '0790000011',
           '0790000012', '0790000013', '0790000014', '0790000015']

def linear_search(l, v):
    for i in range(len(l)):
        if l[i] == v:
            return i
    return None

index = linear_search(names, 'Lyanna')
print(numbers[index])
</template>
</bottom-editor>

  - Schreibe eine Python-Funktion `linear_search(l, v)`. Die Funktion soll in der Liste ''l'' nach dem Wert ''v'' suchen. Falls er gefunden wird, soll __die Position (Index)__ des Elements in der Liste //zurückgegeben// werden (*nicht* geprintet!). 
  - Test: Der Funktionsaufruf `print(linear_search(names, 'Anela'))` soll $1$ ausgeben.
  - Nun wissen wir, dass die gesuchte Dame `Lyanna` (_die Geheimnisvolle_) heisst. Nutze nun diese Funktion, um die Telefonnummer von 'Lyanna' zu ermitteln.

**Achtung:** Generell bei solchen Aufgaben gilt: Verwende **keine vordefinierten Suchfunktionen**. Es geht genau darum, dass du diese *selbst* programmierst.

++++Tipps (zuerst ohne Tipps versuchen!)|
  - Gehe IN der Funktion die Liste `l` alle möglichen Indices (Positionen) durch ([[gf_informatik:programmieren_iii#indirekte_for-schleife|indirekte for-Schleife]]).
  - Vergleiche das Element an jedem Index (also `l[index]`) mit dem gesuchten Wert `v`.
  - Wenn es gleich ist: Gib den Index zurück.
  - Ausserhalb der Funktion: Lese nun aus der **anderen** Liste das Element mit dem eben ermittelten Index aus.
++++

=== Aufgabe A3: Zäh Millione Kombinatione ===
<bottom-exercise id="a3" timeout="180" zip="https://bottom.ch/ksr/1m/null79.py.zip">
<div slot="prompt">
Für das kleine Telefonbuch oben ist es nicht so wichtig, wie schnell der Such-Algorithmus ist. Was aber, wenn wir wirklich alle 10 Millionen Kombinationen durchprobieren?

<p>Für diese Aufgabe benötigst du zusätzlich eine weitere Python-Datei, <code>null79.py</code>, die wir in unserem selbstgeschriebenen Code importieren. Dazu verwenden wir ähnlich wie zu Turtle-Zeiten das Schlüsselwort <code>import</code>.

<p>Verwende deine <code>linear_search()</code> Funktion, um die richtige Telefonnummer von Lyanna herauszufinden. Wie lange dauert die Suche?
</div>
<template data-type="starter">
from null79 import names, numbers

index = 42  # TODO: Suche den Index von Lyanna!
name = names[index]
tel = numbers[index]
print(f'Die Telefonnummer von {name} ist {tel}')
</template>
<template data-type="solution">
from null79 import names, numbers

def linear_search(l, v):
    for i in range(len(l)):
        if l[i] == v:
            return i
    return None

name = 'Lyanna'
index = linear_search(names, name)
if index == None:
    print("Du weisch immer no nüt het si gseit")
else:
    tel = numbers[index]
    print(f'Die Telefonnummer von {name} ist {tel}')
    print("144 hei si gseit!")
    print("Wie isch das nume passiert, hei si gseit.")
    print("Hueresiech, hei si gseit, ey")
</template>
</bottom-exercise>

Oben ist die Datei `null79.py` bereits im gleichen Ordner hinterlegt - wenn du den Code in TigerJython oder VisualStudioCode ausführst, muss die Datei ebenfalls dort abgespeichert werden.

++++ Mit TigerPython / VisualStudioCode :|
Mit [[https://wtp.ethz.ch/#?code=NobwRAdghgtgpmAXGANgezQBwHSYJ5gA0YAJlAC5RJgCMADAEyE00AszLzdAnIQMxMW7FgHYOdcVxod2ArgFYuvFoM5COANn6C6Y-ovoAOLse6LueusaOEzm23poHdHRXPpdLz61dvnLPqYGNFoWrp7hrBKsNGAAvoTg0PDUMFAAlhC4BMRklNQAZgBOaDAABBAArigoItxl6TCYaEXkFbBwAM6EFZUwAEZwRZ0AOhBlY5kkcAAeZQC8ZawMZWUAxGUAKgDyACLbiGUAypUAxgAWcGXT4wCSENNzAG5o4wAyeFAQ0ACEY8lXRYAzrAKazAC6Y3IcBQECKC16AyGILBM0hEEwRUy5AAFAUAOS7dJXTYwuAFV5VGDweEvcYgAFxBqdNogaGwopxfEASniiUgHWoVRqdWyRFIFCoyDWPwA9JVOkVZf1MrL8ORzq8xhsALQAKh1ZVOaBImQA5odKuQCoYyvqdZMmi02uRGnAeiysRAzT00hqxmNTigoJ1OsdMFBhnAAAqaiBwABCGAA1jjuYgxqtViMwDmcwBBMqdCNRsoodIssoaihlIpwciVIoQMMaq51p7IuAkBo3V3kPBlCnwqBlM3pDvjVE9THk9IzLtlADu6X94yzWZHM4Kc-wedzubXq2mBTKAH1T5kV-ecZ0YQVp3XtzN5jndNwc-nM-us7eUAVsKeKBwN6GoIvQdAQZBX7fkWd4AVuc4IghMwBoe1zkmegHAdev4FJ-aHrnWDZNrBf4AUBIHnKh67HphZr1iucAwDhd49Ok-Ewas6Qnv2mBwDi7HMhUaBtNiGYEZxRQZLeZT3I8ACiRQlEUOI5vcTxQOW3aoocOZlAA1EW5Aqex3LQd-3ENGUAA8ZR0OJnEWQZiwUTed5mRJXEnnQNmLOkNllsBbl_hxjlZkRjbjLh8GPohhlDn6OKubh3J2mUNBpekPSvnphmegJEC4n65zYOgZr0ElQUpdyNUGRMkAfuZhHSVccmzIpymqWAbVzGgVplGgJ5Sd6cC6WAdX5aZqFBiGYZHCWt5vBWuKhdm-4FkWC3umUmmYOcUCDK6pyaSgA6dM6C7lpW1ZtNM0JFDAl4sukx01AOEVNmGUBNasAKDi0ZRwFAFyjuOwENA8sw9LMpxwJgbRDjtsGnERZTJnAeCyhpKCVFcEbpEUu7rQeNEYeel7kCxf49BRZoah6cAo_Wp7o3gDNM5T2O4z00zBng8x0Kt37RaevNQAOixi3gP2rCLtOgS5wF01Rnmkf-p63hzLMYwimtEdr0uqyLevM1zgLI_rZsy2rAEvIuMJhos-JQHA6R9fi1si8azavF85CO2UwAg4jIOZEZXpmtgIanOk6SAWg9tFMdMmWSDEAiRDNunnbDvoo5IskH1_RAQH-L9CQBRmigMAYsM5Ae0bcGnhSNQJ8iusXSQwXqznKBhnlTeF5UxddB55m0eeFFU3hDmSfWkVZ_LKvruPZPxjMlO7fth3dzTIbkEL67BpWLn76VbcqR5jmWcf5DADqNDgpnIu950s9hbW88kV7rzndAhWjFVjfIKt9Uq2QYO_MKH0opN1ftbG--974MCfmHH-Pt_7-0gY5aBWc4GqxwSLFu6BE6AJXmhCe9F4xSWhKeAEu8GiHyzHuHMux6xDEehAZaL0ToDkoUMCgVxWztHgDtUSkM5j-WKKUKslwdoaXSMGEeO0UB7QOvWMogwhxXBNpzTSuMibMIgPAk8_l5iLGNozfWrMsFz2IjAsiGtLGmz0XAYxVlbIWK1tY6264WSRjaIsOgPiszAW7OYpuOiDbBNWFvNRATw7mijp0GOcdKiYD4knEMcBgD2U9Ik6OsdTxpIycnOA2BUTdwApEs2OTwTcjzh_MsCJXKxMOlfTiDtRrRKMv43WESnGU1ZnVGg3TQnNKqu5bprT1HmOMvk5JhTilDFKcAPJ3okkpKKek5ZWTyniMqY4rWNS6B1P0jQRADSP7-R1OEhxkShmGRGUY1WGx5rljaKsygrREChJQYVNATS4AAEdKiaR1J0dIAAvBc2IhjYzDINJGS8BongOn1MR91sayhQNbFA4yIA4mmQfa2YSyjFWwLDBROIcRjMNH41oqVZRlnaTBVECJsQCTKLKJlJAWXfj-osIloJxGXKcn5MoABSa41FOKLnOAoq43YAB86UbEwSJX0hx69N4qO3vWHEAI-WOTxYrAlRKjWcVJeSylKAcTdiZSgC1rLxHssKpy7l1wnX8o6M5ZRqjDrCseKK6-7LJXSvwV_cYAIZVHjJqeeifYmLTzYow1Yrp4DYE6EBOGBypZessrxfigkKzCQxWq78UkKytXER1FoXV1KaXSNpcRY0JrGQEjVNx_lbL2W6f5fSpru75pMQsW56t7kY3LYRSNWdqkuOtgQpufDqFwFoR0DtqEqSDGGAieakZbyxleImFMXU3yNW-B0AOe6oxLRZDicCkEII9D4GYPghhlg9HxB8L40AeTxHBEAA|diesem WebtigerPython-Link]] ist die Datei bereits hinterlegt.

Für VisualStudioCode:

Lade die Datei [[https://kantonsschuleromanshorn.sharepoint.com/:u:/s/FSInformatik/EQpO02ZUBldHmbYjEgKka_YBeaBaTHf1IUd-lrtYrdZJkA?download=1|null79.py]] herunter und speichere sie im selben Ordner wie dein Code.
++++

=== Aufgabe A4: Maximal sächsehalb Jahr lang ===
Wir möchten genau wissen, wie lange die Suche dauert, auch wenn es hoffentlich nicht 6.5 Jahre sind.

Um in Python die Zeit zu stoppen, kannst du das `time` Modul verwenden. Wie lange dauert die Suche für die `Lyanna`? Wie lange für `Annina` oder `Zoraya`? Weshalb der Unterschied?

<bottom-exercise id="stopwatch" timeout="180" zip="https://bottom.ch/ksr/1m/null79.py.zip" session="10m">
<template data-type="starter">
import time
# Startzeitpunkt bestimmen
start = time.time()

# TODO: Hier muss die Suche passieren

# Endzeitpunkt bestimmen und Differenz zum Start berechnen
elapsed = time.time() - start
# Ausgabe - das ':.1f' bewirkt die Darstellung mit einer Nachkommastelle
print(f'Vergangene Zeit: {elapsed:.1f}s')
</template>
<template data-type="solution">
from null79 import names, numbers
import time
 
def linear_search(l, v):
    for i in range(len(l)):
        if l[i] == v:
            return i
    return None
 
def stopwatch(name):
    start = time.time()
    index = linear_search(names, name)
    elapsed = time.time() - start
    print(f'Lineare Suche für {name} dauerte {elapsed:.1f}s')
 
stopwatch('Annina')
stopwatch('Lyanna')
stopwatch('Zoraya')
</template>
</bottom-exercise>


=== Aufgabe A5: Umgekehrte Suche ===
Finde heraus, wem die Telefonnummer `0791234567` gehört.

++++Lösung|
Xassemb
++++

<nodisp 1>
++++Code|
<bottom-editor timeout="180" zip="https://bottom.ch/ksr/1m/null79.py.zip" session="10m">
idx = linear_search(numbers, '0791234567')
print(names[idx])
</bottom-editor>
++++
</nodisp>

=== Aufgabe A6: Verbesserte lineare Suche (optional) ===

Wenn wir nach einem Namen suchen, der gar nicht in der Liste vorkommt, z.B. `Alaska`, so dauert die Suche lange, weil die ganze Liste durchsucht wird.

Nun sind die Namen in `null79.names` *alphabetisch sortiert*. Sobald wir einen Namen antreffen, der alphabetisch nach dem gesuchten Wert liegt, können wir die Suche abbrechen. Strings können in Python mit den `>` und `<` Operatoren verglichen werden:

<bottom-editor>
s1 = 'Alaska'
s2 = 'Alberta'
if s1 < s2:
    print(s1 + ' liegt im Alphabet vor ' + s2)
else:
    print(s1 + ' liegt im Alphabet nach ' + s2)
</bottom-editor>

Erweitere deine Funktion `linear_search()` wie folgt:
  * Füge einen Parameter mit Default-Argument `is_sorted=False` hinzu.
  * Wenn die Liste nicht sortiert ist, soll die Suche wie bisher ablaufen.
  * Ist die Liste sortiert, soll die Suche abbrechen, wenn wir im Alphabet bereits weiter sind als der gesuchte Wert.

<nodisp 1>
++++Lösung|
<code python>
def linear_search(l, v, is_sorted=False):
    for i in range(len(l)):
        if l[i] == v:
            return i
        if is_sorted and l[i] > v:
            return None
    return None
</code>
++++
</nodisp>

=== Aufgabe A7: Besserer Algorithmus? (optional) ===

Hast du eine Idee für einen besseren, sprich effizienteren Suchalgorithmus einer bereits sortierten Liste? Bespreche mit der Lehrperson und implementiere danach in Python.


----

Weiter zu [[gf_informatik:suchen_und_sortieren:binaersuche|Binäre Suche]]