# Binary Search
# Binäre Suche setzt voraus, dass die zu durchsuchende Liste sortiert ist.

from random import randint
z = 0

condition = True
while condition:
    n = int(input('Anzahl n der Datenelemente (n < 100): '))
    if n < 100: condition = False

print()    
a = list(range(1,n+1))
for i in range(n): a[i] = randint(0, 99)
print('Quelliste: ')
print(a)

# Sortieren
for j in range(0,n-1):
    min = a[j]
    for i in range(j+1,n):
       if a[i] < min:
           min  = a[i]
           a[i] = a[j]
           a[j] = min

print('sortierte Liste: ')
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(value, array):
   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  value == midvalue: return True
      elif value < midvalue: return binarysearch(value,array[:len(array)//2])
      else:                  return binarysearch(value,array[len(array)//2 + 1:])



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

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

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