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

from random import randint


n=int(input('Anzahl der Datenelemente = '))

a=list(range(1,n+1))

for i in range(0,n):
    a[i]= randint(1,10000)

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(array,value):
     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: '))

# 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')