Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
gf_informatik:suchen_und_sortieren:binaersuche:anleitung [2023-06-06 18:18] – [2: Bedingung der While-Schleife] gragf_informatik:suchen_und_sortieren:binaersuche:anleitung [2025-02-16 08:54] (aktuell) – [3: Wiederholte Schritte in der while-Schleife:] hof
Zeile 1: Zeile 1:
-## Binäre Suche – eine kleine Anleitung+## Binäre Suche – Erklärung und Anleitung
 Wir schreiben eine Funktion namens ''binary\_search(li, el)''. Die Funktion nimmt eine sortierte Liste ''li'' und ein gesuchtes Element ''el'' an. Wenn sie das Element in der Liste findet, gibt sie die Position (den Index) des Elements zurück. Wenn nicht, gibt sie ''None'' zurück. Wir schreiben eine Funktion namens ''binary\_search(li, el)''. Die Funktion nimmt eine sortierte Liste ''li'' und ein gesuchtes Element ''el'' an. Wenn sie das Element in der Liste findet, gibt sie die Position (den Index) des Elements zurück. Wenn nicht, gibt sie ''None'' zurück.
  
Zeile 13: Zeile 13:
 Wir programmieren also einen Algorithnus, bei dem eindeutige Schrite immer wieder durchgeführt werden – solange, bis die Arbeit erledigt ist. Wie bei den meisten Algorithmen sind hierzu zuerst ein paar einmalige Schritte nötig. Dann kommt eine Schleife, in der die Schritte stehen, die wiederholt werden sollen. Wir programmieren also einen Algorithnus, bei dem eindeutige Schrite immer wieder durchgeführt werden – solange, bis die Arbeit erledigt ist. Wie bei den meisten Algorithmen sind hierzu zuerst ein paar einmalige Schritte nötig. Dann kommt eine Schleife, in der die Schritte stehen, die wiederholt werden sollen.
  
-### 1: Einmalige Schritte vor der While-Schleife+### 1: Einmalige Schritte vor der while-Schleife
  
 Nachdem wir den Funktionskopf hingeschrieben haben, legen wir die beiden Variablen ''left'' und ''right'' fest, mit denen wir den Suchbereich abstecken. Zu Beginn ist left 0 und right so gross wie der grösste Index der Liste. Nachdem wir den Funktionskopf hingeschrieben haben, legen wir die beiden Variablen ''left'' und ''right'' fest, mit denen wir den Suchbereich abstecken. Zu Beginn ist left 0 und right so gross wie der grösste Index der Liste.
Zeile 23: Zeile 23:
 </code> </code>
 ++++ ++++
-### 2: Bedingung der While-Schleife +### 2: Bedingung der while-Schleife 
-Wir müssen so lange suchen, wie wir den Suchbereich noch verkleinern können. Es kann sein, dass solange gesucht wird, bis der Suchbereich sich nur noch auf ein einziges Element berschränkt. Dann sind die Variablen ''left'' und ''right'' gleich gross. Wenn hier nichts gefunden wird, müssen wir abbrechen. Wir suchen also solange, wie ''left'' kleiner als oder gleich gross wie ''right'' ist.((Diese Bedingung ist nicht mehr erfüllt, wenn der Vergleich beispielsweise ergibt, dass das gesuchte Element kleiner ist als dasjenige, das hier als einziges übrig bleibt: Denn dann wird die Variable right so verändert, dass sie kleiner wird als left.))+Wir müssen so lange suchen, wie wir den Suchbereich noch verkleinern können. Es kann sein, dass solange gesucht wird, bis der Suchbereich sich nur noch auf ein einziges Element beschränkt. Dann sind die Variablen ''left'' und ''right'' gleich gross. Wenn jetzt nichts gefunden wird, müssen wir abbrechen. Wir suchen also solange, wie ''left'' kleiner als oder gleich gross wie ''right'' ist.((Diese Bedingung ist nicht mehr erfüllt, wenn der Vergleich beispielsweise ergibt, dass das gesuchte Element kleiner ist als dasjenige, das hier als einziges übrig bleibt: Denn dann wird die Variable right so verändert, dass sie kleiner wird als left.))
  
 ++++ Python| ++++ Python|
Zeile 31: Zeile 31:
 </code> </code>
 ++++ ++++
- +### 3: Wiederholte Schritte in der while-Schleife: 
-### 3: Wiederholte Schritte in der While-Schleife: +Zuerst berechnen wir die Mitteposition. Sie ergibt sich aus zwei Schritten: Erstens von der rechten Position die linke abziehen und diesen Wert durch 2 teilen. Zweitens die linke Position hinzuaddieren. Also: ''middle = (right - left) %%//%% 2 + left''. Dieser Term lässt sich in eine einfachere Form bringen: ''middle = (left + right) %%//%% 2''.((Wir verwenden %%//%% statt /, damit unsere Division immer ganze Zahlen und keine Kommazahlen ergibt.))
-Zuerst berechnen wir die Mitteposition. Sie ergibt sich aus zwei Schritten: Erstens von der rechten Position die linke abziehen und diesen Wert durch zwei teilen. Zweitens müssen wir hierzu den linke Position hinzuaddieren. Also: ''middle = left + (right - left) %%//%% 2''. Dieser Term lässt sich in eine einfachere Form bringen:  ''middle = (left + right) %%//%% 2''.((Wir verwenden %%//%% statt /, damit unsere Division immer ganze Zahlen und keine Kommazahlen ergibt.))+
  
 Danach vergleichen wir das Element an der Mitteposition mit dem gesuchten Element. Da es drei Möglichkeiten gibt, ist eine ''if-elif-else''-Verzweigung geeignet: Danach vergleichen wir das Element an der Mitteposition mit dem gesuchten Element. Da es drei Möglichkeiten gibt, ist eine ''if-elif-else''-Verzweigung geeignet:
   * Wenn das Element an der Mitteposition gleich gross ist wie das gesuchte Element, geben wir die Mitteposition zurück.   * Wenn das Element an der Mitteposition gleich gross ist wie das gesuchte Element, geben wir die Mitteposition zurück.
 +  * Wenn das Element an der Mitteposition kleiner ist als das gesuchte Element, befindet sich das gesuchte Element rechts davon. Wir begrenzen den Suchbreich auf die rechte Hälfte, indem wir die Variable ''links'' auf die Mitteposition + 1 setzen.
   * Wenn das Element an der Mitteposition grösser ist als das gesuchte Element, befindet sich das gesuchte Element links davon. Wir begrenzen den Suchbreich auf die linke Hälfte, indem wir die Variable ''rechts'' auf die Mitteposition - 1 setzen.   * Wenn das Element an der Mitteposition grösser ist als das gesuchte Element, befindet sich das gesuchte Element links davon. Wir begrenzen den Suchbreich auf die linke Hälfte, indem wir die Variable ''rechts'' auf die Mitteposition - 1 setzen.
-  * Wenn das Element an der Mitteposition kleiner ist als das gesuchte Element, befindet sich das gesuchte Element links davon. Wir begrenzen den Suchbreich auf die rechte Hälfte, indem wir die Variable ''links'' auf die Mitteposition + 1 setzen. 
  
 ++++ Python| ++++ Python|
Zeile 53: Zeile 52:
  
  
-{{ :gf_informatik:suchen_und_sortieren:binaersuche:pasted:20230605-150804.gif?400|}} In dieser sortierten Liste mit 16 Zahlen wird nach der Zahl 42 gesucht. Der Suchbereich wird duch die Variablen ''l'' und ''r'' (für links und rechts) begrenzt. Zu Beginn erstreckt sich der Suchbereich über die gesamte Liste: ''l'' ist ''0'' und ''r'' ist so gross wie der höchste Index der Liste: ''len(li)-1''.+### 4: Letzer Schritt nach der while-Schleife 
 +Wenn wir uns in der Funktion und nach der while-Schleife befinden, heisst das:  
 +Wir sind nie zur Zeile ''return middle'' gekommen, denn mit ''return'' wird die Funktion verlassen. 
 +Die Bedingung der while-Schleife ist nicht mehr erfüllt, das heisst: es ist kein Suchbereich mehr übrig. 
 +Also geben wir ''None'' zurück. 
 + 
 +++++ Python – Gesamte Funktion| 
 +<code python> 
 +def binary_search(li,el): 
 +    left = 0 
 +    right = len(li)-1 
 +    while left <= right: 
 +        middle = (left + right) //2 
 +        if li[middle] == el: 
 +            return middle 
 +        elif li[middle] < el: 
 +            left = middle + 1 
 +        else: 
 +            right = middle - 1 
 +    return None 
 +</code> 
 +++++
  
  • gf_informatik/suchen_und_sortieren/binaersuche/anleitung.1686075513.txt.gz
  • Zuletzt geändert: 2023-06-06 18:18
  • von gra