# 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('-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```