Python 3 - Lernen und professionell anwenden

Kapitel 7

Sequenzen, Mengen und Generatoren

212

Mit dem Schlüsselwortargument reverse=True sorgen Sie dafür, dass die Liste absteigend

statt aufsteigend sortiert wird:

7.4.5 Binäre Suche in einer sortierten Liste

Wie suchen Sie einen Begriff – sagen wir das Wort »Ordinalzahl« – in einem Wörterbuch?

Man könnte das Wörterbuch vom Anfang an Zeile für Zeile durchlesen und würde sicher-

lich irgendwann (nach vielen Stunden) das Wort »Ordinalzahl« finden.

Vermutlich gehen Sie aber anders vor: Sie schlagen das Wörterbuch ungefähr in der Mitte

auf und landen vielleicht beim Buchstaben »k«. Sie stellen fest, dass Ihr Suchwort im Alpha-

bet weiter hinten liegt, und schlagen nun die zweite Hälfte Ihres Wörterbuches ungefähr in

der Mitte auf. Wahrscheinlich sind Sie nun bei den Wörtern, die mit »s« beginnen. Sie wis-

sen, dass Ihr Suchwort im Alphabet weiter vorne liegt, und schlagen nun eine Seite im drit-

ten Viertel des Buches auf. In dieser Weise fahren Sie fort und engen das Suchintervall

immer weiter ein, bis Sie auf das gesuchte Wort stoßen. Obwohl ein Wörterbuch der deut-

schen Sprache ungefähr 200.000 Stichwörter umfasst, haben Sie in wenigen Sekunden

den gesuchten Begriff gefunden. Diese Technik nennt man »binäre Suche«. Die Idee ist,

dass bei jedem Schritt der Suchbereich halbiert wird.

Die folgende rekursive Funktion prüft, ob das Objekt

x in einer Liste s enthalten ist,

>>> liste

['Zukunft', 'Gegenwart', 'Vergangenheit']

>>> liste.sort(reverse=True)

>>> liste

['Zukunft', 'Vergangenheit', 'Gegenwart']

>>> liste.sort(key=len, reverse=True)

>>> liste

['Vergangenheit', 'Gegenwart', 'Zukunft']

def enthalten(s, x):

pr i n t(s ) #1

if l e n(s ) == 1 : #2

if s[0] == x:

r etu r n Tru e

e l se:

return False

else:

m = s[le n (s) / /2] #3

if x >= m:

return enthalten(s[len(s)//2:], x) # suche rechts weiter

e l se:

return enthalten(s[:len(s)//2], x) # suche links weiter