def search (a, A):

    def linsearch (a, A, i, l):
        # INV: 0<=i<= l = len(A) /\ forall j: 0<=j<i: a =/= A[j] 
        if (a == A[i]):
            return i
        elif (i < l-1):
            return linsearch (a, A, i+1, l)
        else:
            return l
    # end linsearch
    
    l = len(A)
    i = linsearch (a, A, 0, l)
    if (i>=l):
        print 'not found'
    else:
        print 'found at index', i
# end search

import random 
A = random.sample(range(1,99999999), 1000)
print A
search (9999999, A)