#Programmer: Sriram Pemmaraju
#Date: 3-3-2009
#
#Reads a list of integers from a file, followed by an integer provided
#by the user and then searches for that integer in the list. I also
#compute the time it takes to perform the search. It is assumed that the
#input sequence is sorted (in increasing order). This allows me to use
#binary search; in this version I use recursion to implement binary 
#search

import time

#Reads a sequence of integers, separated by spaces, from a file
#which is passed in as an argument to the function. The sequence is
#stored in a list and returned.
def getList1(fileref):

 l = []

 #readlines() returns the contents of file as a list of strings
 #with each line stored in a single string
 t0 = time.time()

 lines = fileref.readlines()
 for s in lines:
   l = l + s.split()
   
 for i in range(0, len(l)):
   l[i] = int(l[i])

 t1 = time.time()

 printNow("Finished reading. Took " + str(t1-t0) + " seconds.")
 return l

#Reads a sequence of integers, separated by spaces, from a file
#which is passed in as an argument to the function. The sequence is
#stored in a list and returned. This function has the same functionality
#as the above function, but creates the list of numbers more efficiently.
def getList2(fileref):
 l = []

 #readlines() returns the contents of file as a list of strings
 #with each line stored in a single string
 t0 = time.time()

 lines = fileref.readlines()
 for s in lines:
   lineList = s.split()
   for num in lineList:
     l.append(num)
   
 for i in range(0, len(l)):
   l[i] = int(l[i])

 t1 = time.time()

 printNow("Finished reading. Took " + str(t1-t0) + " seconds.")
 return l


#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)

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 the sorted list l
def linearSearch(l, x):
 for y in l:
  if(y == x):
   return 1
 return 0

#Starts by asking the user to pick a file consisting of a sequence
#of integers separated by spaces. This sequence is read into a list
#and then the user is asked to input an integer they want searched for.
#Then it calls a binary search function to do the actual search.
#This function is timed.
def search():

  fileref = open(pickAFile(), 'r')
  l = getList2(fileref)

  x = requestInteger("Type an integer you want to search for.")

  t0 = time.time()
  found = binarySearch(l, x)
  t1 = time.time()

  if(found):
    printNow("Found " + str(x))
  else:
    printNow("Not Found " + str(x))

  printNow("It took " + str((t1-t0)) + " seconds to complete the binary search.")

  t0 = time.time()
  found = linearSearch(l, x)
  t1 = time.time()

  if(found):
    printNow("Found " + str(x))
  else:
    printNow("Not Found " + str(x))

  printNow("It took " + str((t1-t0)) + " seconds to complete the linear search.")