# File: searchTest1.py
#
# Testing the correctness of linear search adn binary search.
#

import time
import random

# REPS = 400000
REPS = 10


def linearSearch(A, x):
   for i in range(0,len(A)):
      if A[i] == x: return i
   return -1


# recursively find x in A from A[start] to A[end-1]
#
def binarySearch(A, start, end, x):
   # print("start =", start, "end = ", end)

   # sub-list is empty
   if (start >= end): return -1

   # sub-list has 1 item
   if (start + 1 == end): 
      if A[start] == x:
         return start 
      else:
         return -1

   # divide and conquer

   middle = (end + start)//2
   # print("middle = ", middle)

   if A[middle] == x: 
      return middle
   elif A[middle] > x:
      return binarySearch(A, start, middle, x)
   else:
      return binarySearch(A, middle+1, end, x)


def main():

   aList = [ 0 ] * REPS

   # make new array
   for i in range (0, REPS):
      aList[i] = random.randint(0,REPS)
       
   print(aList)
   aList.sort()
   print(aList)



   start = time.time()

   for i in range(0, 2*REPS):
       x = random.randint(0,REPS)

       found1 = linearSearch(aList, x)
       if (found1 >= 0 and aList[found1] != x):
          print("Houston, we have a problem:", x, found1)

       found2 = binarySearch(aList, 0, len(aList), x)
       if (found2 >= 0 and aList[found1] != x):
          print("Oops:", x, found2)

       if (found1 >= 0 and found2 == -1) or (found1 == -1 and found2 >= 0):
          print("Mmmm..... searches do not agree", x, found1, found2)

   finish = time.time()
   print("Elapsed time =", finish - start, "seconds")
   return

main()