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:34] – [3: Wiederholte Schritte in 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 24: Zeile 24:
 ++++ ++++
 ### 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 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.))+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 36: Zeile 36:
 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|
  • gf_informatik/suchen_und_sortieren/binaersuche/anleitung.1686076456.txt.gz
  • Zuletzt geändert: 2023-06-06 18:34
  • von gra