# Binary Search
# Binäre Suche setzt voraus, dass die zu durchsuchende Liste sortiert ist, und
# entscheidet, ob in einer Liste a von n Datenelementen (hier: Zufallszahlen)
# der für value eingebene Wert enthalten ist.
# Mittels der Zählvariablen z wird die Anzahl der Aufrufe der Funktion
# binarysearch bestimmt.

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,1000)

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 False, falls value als
# Wert einer Komponente des Feldes array nicht vorkommt;
# andernfalls wird der Index derjenigen Komponente des Feldes array,
# deren Wert mit value übereinstimmt, der als global definierten
# Variablen index zugewiesen.

def binarysearch(array, value, begin, end):
     global index
     global z
     z +=1
     print(array[begin:end+1])
     if begin > end: return False
     middle = (begin + end) // 2
     print('mittleres Element:  a[',middle,'] = ',array[middle])
     if array[middle] == value:
        index = middle
     elif array[middle] < value:
        return binarysearch(array, value, middle + 1, end)
     else:
        return binarysearch(array, value, begin, middle - 1)


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

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

if binarysearch(a, value, 0, len(a)-1) == False:
    print(value,'wurde nicht gefunden')
else:
    print(value,'wurde gefunden an der Stelle', index)
    print('a[',index,'] = ',a[index])

print('# Aufrufe binarysearch =',z)