#Programmer: Sriram Pemmaraju
#Date: 2-19-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.

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 getList(fileref):

 l = []

 #readlines() returns the contents of file as a list of strings
 #with each line stored in a single string
 lines = fileref.readlines()
 for s in lines:
   l = l + s.split()
   
 for i in range(0, len(l)):
   l[i] = int(l[i])

 return l

#Performs a binary search for x on the sorted list l
def binarySearch(l, x):
 first = 0
 last = len(l)-1

 #Main loop: in each iteration x is compared with the
 #the element in the middle of the current sublist. Depending
 #on the outcome of the comparison, we work with the left sublist
 #or right sublist in the next iteration
 while(first <= last):
  mid = (first + last)/2
  if(x == l[mid]):
   return 1

  if(x < l[mid]):
   last = mid - 1
  else: 
   first = mid + 1

 #The sublist has shrunk to size 0 and so x is not in the list
 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 = getList(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 search.")