# Measures the runtime of an algorithm to
# binary search a list for a given value.

import random
import time

# Sequential search algorithm.
# Returns the index at which the given target number first
# appears in the given input list, or -1 if it is not found.
def sequential_search(elements, target):
    for i in range(len(elements)):
        if elements[i] == target:
            return i
    return -1   # not found

# Binary search algorithm.
# Returns an index at which the target appears
# in the given input list, or -1 if not found.
# Precondition: list is sorted.
def binary_search(numbers, target):
    start = 0
    end = len(numbers) - 1
    while start <= end:
        mid = (start + end) // 2
        if target == numbers[mid]:
            return mid        # found it!
        elif target < numbers[mid]:
            end = mid - 1     # go left
        else:
            start = mid + 1   # go right
    return -1                 # not found

# Recursive binary search algorithm.
# Returns an index at which the target appears
# in the given input list, or -1 if not found.
# Precondition: list is sorted.
def binary_search_r(numbers, target, start = 0, \
                    end = len(numbers) - 1):
    if start > end:
        return -1   # not found
    else:     
        mid = (start + end) // 2
        if target == numbers[mid]:
            return mid        # found it!
        elif target < numbers[mid]:
            # too small; go left
            return binary_search_r(numbers, target, start, mid - 1)
        else:
            # too large; go right
            return binary_search_r(numbers, target, mid + 1, end)

# Creates and returns a random list of integers of length N.
def create_random_list(N):
    numbers = [0] * N
    for i in range(N):
        if i != N // 2:
            numbers[i] = random.randint(0, 999999999)
    return numbers

def create_sorted_list(N):
    numbers = [0] * N
    for i in range(N):
        if i != N // 2:
            numbers[i] = random.randint(0, 999999999)
    numbers.sort()
    return numbers

def main():
    # Search for a word's index many times
    N = 1000000
    MAX_N = 32000000
    print("N", "runtime (ms)", sep="\t")
    while N <= MAX_N:
        numbers = create_sorted_list(N)
        
        start_time = time.time()
        index1 = binary_search_r(numbers, 0)
        elapsed_time1 = time.time() - start_time
        
        start_time = time.time()
        index2 = binary_search_r(numbers, -5)
        elapsed_time2 = time.time() - start_time
        
        print(N, round(elapsed_time1 * 1000), round(elapsed_time2 * 1000), sep="\t")
        N *= 2

main()