Binäre Suche

Die binäre Suche ist ein effizienterer Suchalgorithmus als die lineare Suche. Um die binäre Suche an-zuwenden muss das Array sortiert sein (siehe Informationsmaterial L2_2.1).

Vorgehensweise:

  1. Setze den Start s auf das erste und das Ende e auf das letzte Element im Array.
  2. Ermittle die Mitte m zwischen Start und Ende. (Achtung ggf. abrunden; siehe unten)
  3. Wenn gesuchtes Element Element m, dann setze e auf m - 1
  4. Wenn gesuchtes Element > Element m, dann setze s auf m + 1
  5. Wenn gesuchtes Element = Element m, dann Suche erfolgreich!
  6. Wiederhole ab Schritt 2

Beispiel:

Gesucht wird die Zahl 42

Bereits nach 3 Vergleichen wurde das gesuchte Element gefunden. Bei der linearen Suche wäre das gesuchte Element erst nach 8 Vergleichen gefunden worden.

Runden von Zahlen in Python

Eine Dezimalzahl kann in Python in eine ganze Zahl abgerundet werden, indem die Dezimalzahl in eine Zahl vom Typ Integer umgewandelt wird.

Beispiel:

int(7.98) ⇒ 7

int(9.07) ⇒ 9

Umsetzung

Aufgaben

Lösungen