import random
import time

n = 1000000

A = []
i = 0
while i < n:
    r = random.randint(1, n)
    A.append(r)
    #print(A)
    i += 1
A.sort()

x = n // 3

#print(x, A)

###########################################################

if True:
    print('Linear search')

    i = 0
    position = None

    start = time.time()
    while i < len(A):
        if A[i] == x:
            position = i
            break

        #print(i, A[i], position)
        i += 1
    end = time.time()

    if position != None:
        print(x, 'står på position', position)
    else:
        print(x, 'er ikke i listen')

    print('time =', end - start)

###########################################################

print('Binary search')

low = 0
high = len(A)

start = time.time()
j = 0
while j < 10000:
    while low < high:
        mid = (low + high) // 2
        #print(low, mid, high, A[mid])

        if A[mid] < x:
            low = mid + 1
        else:
            high = mid 
    j += 1
end = time.time()

if high < len(A) and A[high] == x:
    print(x, 'står på position', high)
else:
    print(x, 'er ikke i A')

print('time =', end - start)