"""
 searching.py

 examples of searching a list for a given value

     $ python searching.py 
     -- searching.py --
     a random array: [46, 60, 40, 46, 59, 50, 63, 38]
     linear search for 10 in [5, 8, 10, 20, 30] : i=2.
     binary search for 10 in [5, 8, 10, 20, 30] : i=2.
      n_trials=2, elapsed=0.0
      n_trials=4, elapsed=0.0719606876373291
      n_trials=8, elapsed=0.14397525787353516
      n_trials=16, elapsed=0.2801327705383301
      n_trials=32, elapsed=0.5522933006286621
     time for linear n=1000000 is 0.03455341.
      n_trials=2, elapsed=0.0
      n_trials=4, elapsed=4.00543212890625e-05
      n_trials=8, elapsed=5.2928924560546875e-05
      n_trials=16, elapsed=5.1975250244140625e-05
      n_trials=32, elapsed=7.605552673339844e-05
      n_trials=64, elapsed=0.00010013580322265625
      n_trials=128, elapsed=0.00016188621520996094
      n_trials=256, elapsed=0.00029778480529785156
      n_trials=512, elapsed=0.0005388259887695312
      n_trials=1024, elapsed=0.0011131763458251953
      n_trials=2048, elapsed=0.0021419525146484375
      n_trials=4096, elapsed=0.004206180572509766
      n_trials=8192, elapsed=0.008191108703613281
      n_trials=16384, elapsed=0.01651906967163086
      n_trials=32768, elapsed=0.031621694564819336
      n_trials=65536, elapsed=0.06403422355651855
      n_trials=131072, elapsed=0.12969589233398438
      n_trials=262144, elapsed=0.2576608657836914
      n_trials=524288, elapsed=0.515794038772583
     time for binary n=1000000 is 0.00000196.

 Jim Mahoney | cs.bennington.college | MIT License | Feb 2022
"""
from random import randint
from time import time

def search_linear(x, items):
    """ search for x in items. If found, return its index; else return None """
    # Implemented with a linear i.e. items[0], items[1], ... search.
    # Quick quiz: what O() behavior do you expect this to have?
    for i in range(len(items)):   # Look at each array item in turn.
        if items[i] == x:         #   Found x; return the index.
            return i
    return None                   # Looked at all of 'em; x not found.

def search_binary(x, items):
    """ search for x in an ordered list. Return its index if found else Nonen """
    # Implemented with a binary search in an explicit loop.
    # Quick quiz: what O() behavior do you expect this to have?
    i_low = 0
    i_high = len(items) - 1
    while i_low <= i_high:           # Still a range of indeces to search?
        i_mid = (i_low + i_high)//2  # Index of middle of remaining range.
        item = items[i_mid]
        if x == item :               # Found it! Return the index.
            return i_mid
        elif x < item:               # x is in lower half of range, so
            i_high = i_mid - 1       #     move top marker down.
        else:                        # x is in upper half, so
            i_low = i_mid + 1        #     move bottom marker up.
    return None                      # No place left to search => x is missing.

def get_small_large(n):
    """ return (smallest, largest) used by the other functions here """
    return (1, n*n)

def random_numbers(n):
    """ return a list of of n random integers """
    (smallest, largest) = get_small_large(n)
    result = [0] * n                # allocate an empty indexed array
    for i in range(n):              # fill it with randoms
        result[i] = randint(smallest, largest)
    return result

def random_number(n):
    """ return a random integer """
    (smallest, largest) = get_small_large(n)
    return randint(smallest, largest)

def average_time(func, n, verbose=False):
    """ Return the average time it takes to run func(x, random_numbers(n)) """
    # If the function runs too fast, we run it in many trials, then
    # divide by the number of trials in order to get reasonable timing.
    n_trials = 1
    elapsed_seconds = 0.0
    enough_seconds = 1.0
    while elapsed_seconds < enough_seconds:
        n_trials = n_trials * 2
        numbers = sorted(random_numbers(n))  # in case we do binary search
        number = random_number(n)
        start = time()
        if verbose:
            print(f" n_trials={n_trials}, elapsed={elapsed_seconds}")
        for i in range(n_trials):
            result = func(number, numbers)
        stop = time()
        elapsed_seconds = stop - start
    return elapsed_seconds / n_trials

def main():
    print("-- searching.py --")
    print(f"a random array: {random_numbers(8)}")
    x = 10
    xs = [5, 8, 10, 20, 30]
    print(f"linear search for {x} in {xs} : i={search_linear(x, xs)}.")
    print(f"binary search for {x} in {xs} : i={search_binary(x, xs)}.")
    n = 1000000
    linear_time = average_time(search_linear, n, verbose=True)
    print(f"time for linear n={n} is {linear_time:.8f}.")
    binary_time = average_time(search_binary, n, verbose=True)    
    print(f"time for binary n={n} is {binary_time:.8f}.")    

if __name__ == "__main__":
    main()