Untitled
unknown
plain_text
3 years ago
4.5 kB
2
Indexable
Never
# -*- 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