# Binary Search
# Binäre Suche setzt voraus, dass die zu durchsuchende Liste sortiert ist.
# Wir fragen, ob in einer Liste von n Zufallszahlen ein bestimmter Wert enthalten ist.

from random import randint
z = 0

a = [3, 4, 5, 5, 7, 8, 11, 13, 19, 21]
   
print('Quelliste: ')
print(a)

print()


# binarysearch liefert den Booleschen Wert True, falls value als
# Inhalt einer Komponente des Arrays array vorkommt,
# andernfalls liefert binarysearch den Booleschen Wert False.

def binarysearch(array,value):
     global z
     z += 1
     print(array)
     if array == [] or (len(array) == 1 and array[0] !=  value):
         return False
     else:
         midvalue = array[len(array)//2]
         if midvalue == value:
             return True
         elif value < midvalue:
             return binarysearch(array[:len(array)//2],value)
         else:
             return binarysearch(array[len(array)//2 + 1:],value)



value = int(input('gesuchte Zahl: '))
print()

# Aufruf der Funktion binarysearch
# zur Suche von value innerhalb des Arrays a

if binarysearch(a,value) == True: print(value,'wurde gefunden')
else: print(value,'wurde nicht gefunden')
print('# Aufrufe binarysearch =',z)