from random import randint
z = 0

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

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

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

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()
value = int(input('gesuchte Zahl: '))

# Falls value als Inhalt einer Komponente des Arrays a vorkommt,
# liefert binarysearch den Index der betreffenden Komponente,
# andernfalls: 'nicht gefunden'


def binarysearch(array, x, l, r):
    global z
    z += 1
    if l > r: return 'nicht gefunden'
    middle = (l + r) // 2
    if array[middle] == x:
        return middle
    elif array[middle] < x:
        return binarysearch(array, x, middle + 1, r)
    else:
        return binarysearch(array, x, l, middle - 1)


index = binarysearch(a, value, 0, len(a)-1)

if index == 'nicht gefunden': print(index)
else: print('gefunden bei index =',index)

print('Anzahl der Aufrufe binarysearch: ',z)