Suche in Arrays

Die folgende Funktion sucht ein gegebenes Element x in einem Array a und gibt True aus, falls x in a enthalten ist, und sonst False.

def has_element(a, x):
  found = False              #1
  for i in range(0,len(a)):  #2
    if x == a[i]:            #3
      found = True           #4
  return found               #5

Die folgende Programmtabelle dokumentiert die Ausführung dieses Programms für die Argumente a = [1,2,3,4,5] und x = 3. Wir verzichten dabei auf die Angabe der Werte für x und a, die sich während der Ausführung nicht ändern:

PPfoundix == a[i]Rückgabewert
#1False
#20
#3False
#21
#3False
#22
#3True
#4True
#23
#3False
#24
#3False
#5True

Wie wir sehen, durchläuft das Programm das gesamte Feld auch dann, wenn das Element schon gefunden wurde. Mit einer while-Schleife können wir erreichen, dass die Suche in diesem Fall beendet wird:

def has_element(a, x):
  found = False                                       #1
  i = 0                                               #2
  while not found and i < len(a):                     #3
    found = x == a[i]                                 #4
    i = i + 1                                         #5
  return found                                        #6

Die folgende Programmtabelle dokumentiert die Ausführung dieses Programms für die gleiche Eingabe.

PPfoundinot found and i < len(a)Rückgabewert
#1False
#20
#3True
#4False
#51
#3True
#4False
#52
#3True
#4True
#53
#3False
#6True

Wie wir sehen, bricht das Programm nun ab, wenn das gesuchte Element gefunden wurde.