"""Given a list L of integers starting with a negative and
ending with a positive integer, and where |L[i+1] - L[i]| <= 1,
find the position of a zero in L.
"""

def find_zero_loop(L):
    i = 0
    while L[i] != 0:
        i += 1
    return i

def find_zero_enumerate(L):
    for idx, e in enumerate(L):
        if e == 0:
            return idx

def find_zero_index(L):
    return L.index(0)

def find_zero_binary_search(L):
    low = 0
    high = len(L) - 1
    while True: # L[low] < 0 < L[high]
        mid = (low + high) // 2
        if L[mid] == 0:
            return mid
        elif L[mid] < 0:
            low = mid
        else:
            high = mid

def find_zero_recursive(L):
    def search(low, high):
        mid = (low + high) // 2
        if L[mid] == 0:
            return mid
        elif L[mid] < 0:
            return search(mid, high)
        else:
            return search(low, mid)

    return search(0, len(L)-1)

L = [-5, -4, -3, -3, -4, -3, -2, -1, 0, 1, 2, 1, 0, -1, -2, -1, 0 , 1, 2, 3, 2]

print("loop:", find_zero_loop(L))
print("enumerate:", find_zero_enumerate(L))
print("index:", find_zero_index(L))
print("binary search:", find_zero_binary_search(L))
print("reecursive binary search:", find_zero_recursive(L))

import matplotlib.pyplot as plt

plt.plot([0,len(L)-1],[0,0]) # horizontal line at y=0
plt.xticks(range(len(L)))
plt.plot(L)
plt.plot(L, "ro")
plt.show()

n = 1000000

L = list(range(-n,n+1)) + list(range(n,-2*n,-1)) + list(range(-2*n, 3*n))

import time

for f in [ find_zero_loop, find_zero_enumerate, find_zero_index,
           find_zero_binary_search, find_zero_recursive ]:
    start = time.clock()
    f(L)
    end = time.clock()
    print(f, end - start)


