import time
import random

#Performs a binary search for x on the sorted list l.
#This is just a "wrapper" function that sets up the recursive
#call.
def binarySearch(l, x):
 first = 0
 last = len(l)-1
 return recursiveBinarySearch(l, first, last, x)

#This is the recursive binary search function. The arguments to this
#function are not only the list l, and the element x, but also first
#and last, indices that specify the boundaries of the array.
def recursiveBinarySearch(l, first, last, x):
 #Base case 1, the sublist has shrunk to size 0 and
 # the search is unsuccessful
 if(first > last):
  return 0

 #Two Recursive cases, one for when x is smaller than
 #l[mid] and the other when x is larger than l[mid]
 mid = (first + last)/2
 if(x < l[mid]):
  return recursiveBinarySearch(l, first, mid-1, x)
 if(x > l[mid]):
  return recursiveBinarySearch(l, mid+1, last, x)
 #Base case 2, search is successful
 else:
  return 1

#Performs linear search for x on a prefix l[0..last-1] 
#of the given list l,
def linearSearch(l, x, last):
 for index in range(0, last):
  if(l[index] == x):
   return 1
 return 0

def main():
 
 #Generating the list we will search
 numList = []
 for i in range(0, 1000000):
  numList.append(random.random())
 numList.sort()

 for n in range(100000, 1050000, 50000):
  sumBinaryTime =  0
  sumLinearTime = 0
  for i in range(0, 100):
   x = random.random()
   
   sbt = time.time()
   binaryFound = recursiveBinarySearch(numList, 0, n-1, x)
   ebt = time.time()
   elapsedBinaryTime = ebt - sbt

   slt = time.time()
   linearFound = linearSearch(numList, x, n)
   elt = time.time()
   elapsedLinearTime = elt - slt
 
   sumBinaryTime += elapsedBinaryTime
   sumLinearTime += elapsedLinearTime
  
  print(str(sumBinaryTime) + " " + str(sumLinearTime))