# SelectionSort
# Aufwand = O(n^2)
# BinarySearch
# Aufwand = O(log(n))

from random import randint
import time

z = 0
x = 0

n = int(input('Laenge des arrays: '))
print()


# Erzeugen des arrays mit dem Namen a 
# und den n Komponenten a[0], . . . , a[n-1]
a = list(range(1,n+1))

# Zuweisung von Zufallszahlen an die Komponenten des arrays a
for i in range(0,n):
    a[i] = randint(1,10000000)

# Ausgabe der Quelliste
r = int(input('Wieviele Elemente sollen angezeigt werden? '))
print()
for i in range(0,r):
    print(a[i])


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

def binarysearch(array,value):
     global z
     z += 1
     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)
            

def selectionsort():
    global x   
    j = 0
    while j <= len(a)-2:
       i = j + 1
       min = a[j]
       while i < len(a):
          x += 1
          if a[i] < min:
              min = a[i]
              a[i] = a[j]
              a[j] = min
          i = i + 1
       j = j + 1
  
 
  
start = time.time()

selectionsort() 

end = time.time()


print()
print('Sortierte Liste:')
print()
for i in range(0,r):
    print(a[i])
    
print()
print('Zeitaufwand zum Sortieren von',n,'Elementen: {:7.3f} s'.format(end-start))
print('Anzahl Durchlaeufe der inneren Schleife:  ',x)
print()    
value = int(input('gesuchtes Element: '))
print()

# Aufruf der Funktion binarysearch zur Suche von value im Array a

start = time.time()

result = binarysearch(a,value)

end = time.time()


if result == True:
    print(value,'wurde gefunden')
else:
    print(value,'wurde nicht gefunden')

print()
print('Zeitaufwand BinarySearch bei',n,'Elementen: {:7.3f} s'.format(end-start))
print('# Aufrufe binarysearch: ',z)