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 [2024-01-22 09:44] – [2: Bedingung der while-Schleife] hofgf_informatik:suchen_und_sortieren:binaersuche:anleitung [2025-02-16 08:54] (aktuell) – [3: Wiederholte Schritte in der while-Schleife:] hof
Zeile 30: Zeile 30:
 while left <= right:  while left <= right: 
 </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 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.))
Zeile 37: 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.1705916674.txt.gz
  • Zuletzt geändert: 2024-01-22 09:44
  • von hof