# To prove binary search is faster than naive search!

# Naive search: scan entire list and ask if its equal to the target
# If yes, then return the index
# If no, return -1
import random
import time


def naive_search(l, target):
    for i in range(len(l)):
        if l[i] == target:
            return i

    return -1


# Binary search uses divide and conquer!
# We will leverage the fact that our list is SORTED.

def binary_search(l, target, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(l) - 1

    if high < low:
        return high, low

    midpoint = (low + high) // 2  # 2

    if l[midpoint] == target:
        return midpoint
    elif target < l[midpoint]:
        return binary_search(l, target, low, midpoint-1)
    else:
        # target > l[midpoint]
        return binary_search(l, target, midpoint+1, high)


if __name__ == '__main__':
    # Sorted List
    length = 1000
    sorted_list = set()
    while len(sorted_list) < length:
        sorted_list.add(random.randint(-3*length, 3*length))
    sorted_list = sorted(list(sorted_list))

    start = time.time()
    for target in sorted_list:
        naive_search(sorted_list, target)
    end = time.time()
    print("Naive search time: ", (end-start)/length, "seconds")

    start = time.time()
    for target in sorted_list:
        binary_search(sorted_list, target)
    end = time.time()
    print("Binary search time: ", (end - start) / length, "seconds")
