#!/usr/bin/python3

# SI 335: Computer Algorithms
# Unit 1

from math import floor
import random

def linearSearch(A, x):
    i = 0
    while i < len(A) and A[i] < x:
        i = i + 1
    if i < len(A) and A[i] == x: return i
    else: return 'NOT FOUND'


def binarySearch(A, x, left=0, right=None):
    if right is None: right = len(A) - 1
    while left < right:
        middle = floor((left + right) / 2)
        if x <= A[middle]:
            right = middle
        elif x > A[middle]:
            left = middle+1
    if A[left] == x: return left
    else: return 'NOT FOUND'


def gallopSearch(A, x):
    i = 1
    while i < len(A) and A[i] <= x:
        i = i * 2
    left = floor(i / 2)
    right = min(i, len(A)) - 1
    return binarySearch(A, x, left, right)


# This is provided for testing purposes.
def randomSortedArray(size, maxval):
    return sorted(random.sample(range(maxval), size))

def searchTest():
    searchAlgs = [linearSearch, binarySearch, gallopSearch]
    allgood = True
    data = randomSortedArray(10000, 10000000)
    i = random.randrange(len(data))
    val = random.choice(data)
    while val in data:
        val += 1
    for alg in searchAlgs:
        good = (
            alg(data, -10) == 'NOT FOUND' and
            alg(data, data[i]) == i and
            alg(data, data[0]) == 0 and
            alg(data, data[-1]) == len(data)-1 and
            alg(data, val) == 'NOT FOUND'
        )
        if not good:
            print("FAILED CHECK for", alg.__name__)
            allgood = False
    return allgood

if __name__ == '__main__':
    if searchTest():
        print("All checks passed!")