A = [1, 3, 5, 8, 10, 11, 13, 17, 20, 21]  # sorteret

x = 100  # element vi søger efter

# Invariant:
# A = [x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x]
#                        |        |              |
#                       low      mid            high
#      ----- < x------|                          |-------- >= x ---

low = 0
high = len(A)

while low < high:
    mid = (low + high) // 2
    #print(low, mid, high, A[mid])

    if A[mid] < x:
        low = mid + 1
    else:
        high = mid 

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