{
"cells": [
{
"cell_type": "markdown",
"id": "16521a41-5c39-4cb3-b26a-37f2f746863e",
"metadata": {
"tags": []
},
"source": [
"## Sequentielle Suche versus Binäre Suche\n",
"\n",
"Python bietet einige vorprogrammierte Suchmethoden auf Listen. Wir werden hier zwei unterschiedliche Suchstrategien selbst implementieren.\n",
"\n",
"Zuerst implementieren wir eine Funktion ```sequential_search```. Dabei beginnen wir die Suche an einem Ende der Liste und gehen dann Schritt für Schritt alle Elemente der Liste durch. Dabei wird jeweils geprüft ob der zu suchende Wert dem aktuellen Element entspricht und folglich in der Liste vorkommt.\n",
"\n",
"Die zweite Funktion ```binary_search``` setzt eine sortierte Liste voraus. Dadurch lässt sich der Suchbereich schnell halbieren indem man nachsieht, welcher Wert in der Mitte der Liste zu finden ist. \n",
"\n",
"Zur Vorbereitung implemetieren wir eine Funtion ```simple_data_generator```die uns eine einfache Liste der Länge ```n``` erzeugt. Damit lässt sich leicht überpfrüfen, ob unsere Suchalgorithmen korrekt arbeiten. Wir speichern in der Liste die Zahlen von $0$ bis $n-1$, so dass der Index mit dem Eintrag in der Liste übereinstimmt.\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "5a3092f3-9610-4d1a-baf5-14c6a4b0a024",
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n"
]
}
],
"source": [
"def simple_data_generator(n):\n",
" \n",
" pass # Durch die Implementierung zu ersetzen!\n",
" \n",
"simple_data = simple_data_generator(10)\n",
"print( simple_data)"
]
},
{
"cell_type": "markdown",
"id": "a52121b2-0634-4a72-94e9-8996e641064b",
"metadata": {},
"source": [
" \n",
"\n",
"\n",
"\n",
"Nun werden wir eine Funktion ```sequential_search``` implementieren, die als ersten Parameter eine Liste ```list ``` und als zweiten Parameter einen Wert ```val``` erwartet. Der Rückgabewert der Funktion soll der erste Index sein bei dem ```val``` in der Liste ```list ``` gefunden wird. Falls der Wert in der Liste nicht vorkommt soll ```None ``` zurückgegeben werden."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "5cf124cb-081a-4bd5-80c3-b175e6f968ed",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n"
]
}
],
"source": [
"def sequential_search(list, val):\n",
" \n",
" pass # Durch die Implementierung zu ersetzen!\n",
"\n",
"\n",
"index = sequential_search(simple_data,10)\n",
"print(index)\n",
" "
]
},
{
"cell_type": "markdown",
"id": "a2434843-8e38-45e3-b980-5747ee1a6db5",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "e4139193-0bed-4a41-bc6c-14bba6ae71e0",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n"
]
}
],
"source": [
"def binary_search(list, val):\n",
" \n",
" pass # Durch die Implementierung zu ersetzen!\n",
"\n",
"index = binary_search(simple_data, 13)\n",
"print(index)"
]
},
{
"cell_type": "markdown",
"id": "673b0812-4330-4a15-8e87-1905593c3387",
"metadata": {},
"source": [
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "dcca5900-3fec-4e66-9bd2-8c7ad837b700",
"metadata": {},
"source": [
"#### Rekursive Implementierung \n",
"\n",
"Die obige Implementierung bezeichnet man als eine iterative Lösung. Man kann die ```Binäre Suche``` jedoch auch rekursiv implementieren. Hierzu implementieren wir eine Funktion ```binary_recursive(list,low,high,val)``` die ausser der zu durchsuchenden Liste und dem gesuchten Wert noch die Parameter ```low``` and ```high``` enthält. Damit kann die Suche in der Liste auf den Bereich zwischen ```low``` und ```high``` begrenzt werden. Die Funktion kann sich somit selbst auf einem Unterbereich der Liste aufrufen.\n",
"\n",
"Das Prinzip rekursiver Algorithmen hat folgende Stuktur:\n",
"\n",
"```python\n",
"if (problem_klein_genug):\n",
" nicht_rekusiver_Zweig\n",
"else:\n",
" rekursiver_Zweig\n",
"```\n",
"<div class=\"alert alert-block alert-success\">\n",
"ACHTUNG: Vergessen sie nicht das Abbruchkriterium der Rekursion, sonst ergibt sich eine Endlosschleife!\n",
"</div>\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "58cd7053-75c0-4cfb-893f-408bad981231",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n"
]
}
],
"source": [
"def binary_recursive(list, low, high, val):\n",
" \n",
" pass # Durch die Implementierung zu ersetzen!\n",
" \n",
"print( binary_recursive( simple_data, 0, len(simple_data)-1, 1) )\n"
]
},
{
"cell_type": "markdown",
"id": "897530bb-5e29-4787-9015-7bb661f93f39",
"metadata": {},
"source": [
"#### Bermerkung zum \"=\" Operator bei Listen!\n",
"\n",
"Wir wollen in diesem Beispiel sehen, wie sich Listen verhalten wenn wir den Zuweisungsoperator `=` verwenden."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "98eff05c-7b98-4e65-a485-f56f5ea36b46",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"y = 42 , x = 1\n"
]
}
],
"source": [
"x = 1\n",
"y = x\n",
"y = 42\n",
"print(\"y =\", y, \", x = \", x)\n",
"\n",
"pass # Hier folgt eine equivalente Implementierung für Listen \n",
"\n",
"\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3.8 (standard)",
"language": "python",
"name": "python3.8"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.11"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": false,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": false,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 5
}