# -*- coding: utf-8 -*-
#argparse allows the parsing of command line arguments
import argparse
#utility functions for cs 6515 projects
import ProjectUtils as util
"""
findX.py - Intro to Graduate Algorithms, Summer 2020
Solve the findX in an Infinite array problem using a Divide & Conqueor method
Your runtime must be O(log n)
The array of values is indexed A[1..n] inclusive
Your code MUST NOT directly reference any variables in findX. The following methods are available:
findX.start(seed) -- returns the value (x) to search for within the array
findX.lookup(i) -- returns A[i] or None if i>n
findX.lookups() -- returns the number of calls to lookup
"""
def findXinA(x, findX):
#TODO Your Code Begins Here, DO NOT MODIFY ANY CODE ABOVE THIS LINE
theIndex = -1
low = 0
high = 1
# this loop fixes the lower and higher index in the array A where we need to look
while True:
temp = findX.lookup(high-1)
if temp == None:
high = high - 1
break
if temp == x:
theIndex = high-1
break
if temp < x:
low = high
high = 2 * high
else:
high = high - 1
break
# if we haven't yet found the element then do a binary search in range A[low, high]
if theIndex == -1:
while low <= high:
mid = (low + high) // 2
temp = findX.lookup(mid)
if temp == None or temp > x:
high = mid - 1
elif temp == x:
theIndex = mid
break
else:
low = mid + 1
#TODOne Your code Ends here, DO NOT MOIDFY ANYTHING BELOW THIS LINE
numLookups = findX.lookups()
return theIndex, numLookups
def main():
"""
main - DO NOT CHANGE ANYTHING BELOW THIS LINE
"""
# DO NOT REMOVE ANY ARGUMENTS FROM THE ARGPARSER BELOW
parser = argparse.ArgumentParser(description='Find X Coding Quiz')
#args for autograder, DO NOT MODIFY ANY OF THESE
parser.add_argument('-n', '--sName', help='Student name, used for autograder', default='GT', dest='studentName')
parser.add_argument('-a', '--autograde', help='Autograder-called (2) or not (1=default)', type=int, choices=[1, 2], default=1, dest='autograde')
parser.add_argument('-s', '--seed', help='seed value for random function', type=int, default=123456, dest='seed')
parser.add_argument('-l', '--nLower', help='lower bound for N', type=int, default=10, dest='nLower')
parser.add_argument('-u', '--nUpper', help='upper bound for N', type=int, default=100000, dest='nUpper')
args = parser.parse_args()
#DO NOT MODIFY ANY OF THE FOLLOWING CODE
findX = util.findX()
x = findX.start(args.seed, args.nLower, args.nUpper)
index, calls = findXinA(x, findX)
print('findX result: x found at index {} in {} calls'.format(index, calls))
return
if __name__ == '__main__':
main()
# -*- coding: utf-8 -*-
#import time
#import os
#useful structure to build dictionaries of lists
#from collections import defaultdict
########################################
#IO and Util functions
#returns sorted version of l, and idx order of sort
import random
import math
import sys
class findX():
def __init__(self):
self.__A = []
self.__n = 0
self.x = 0
self.__lookupCount=0
self.__maxCalls = 0
return
def start(self, seed, nLower=10, nUpper=100000):
random.seed(seed)
self.__lookupCount=0
self.__n = random.randint(nLower, nUpper)
self.__A = random.sample(range(nUpper*2), self.__n+1) # sample extra value to avoid A[n] error
self.__A.sort()
self.x = self.__A[random.randint(1,self.__n)]
self.__maxCalls = int(math.log(self.__n, 2)*2) + 2
return self.x
def lookup(self, i):
self.__lookupCount += 1
if self.__lookupCount > self.__maxCalls:
raise Exception("Exceeded Maximum Number of Lookups")
if i > self.__n:
return None
else:
return self.__A[i]
def lookups(self):
return self.__lookupCount
#End findXinA functions
#################################
Step-by-step explanation
Reference for binary search simulation for better understanding: https://www.cs.usfca.edu/~galles/visualization/Search.html