'''
Created on Nov 21, 2011

@author: rodger
'''

import time

def linear_search1(v, L):
    # return index of first occurence of v in L
    i = 0
    while i != len(L) and L[i] != v:
        i = i+1
    return i

def linear_search2(v, L):
    # return index of first occurrence of v in L
    i = 0
    for value in L:
        if value == v:
            return i 
        i = i+1
    return len(L)

def linear_search3(v,L):
    if len(L)>0:
        if v == L[0]:
            return 0
        else:
            return 1 + linear_search3(v, L[1:])
    return 0

def binary_search(v,L):
    i = 0
    j = len(L) - 1
    while i != j+1:
        m = (i+j)/2
        if L[m] < v:
            i = m+1
        else:
            j = m-1
    if 0 <= i < len(L) and L[i] == v:
        return i 
    else: 
        return -1
   
def main():
    filename = "../data/numbers2.txt"
    file = open(filename)
    nlist = [int(num.strip()) for num in file]
    file.close()   
    v = 54
    functions = [linear_search1, linear_search2, linear_search3]
    for f in functions:
        start = time.time()
        answer = f(v,nlist)
        end = time.time()
        print "found at ", answer, " in ", end - start

main()