Untitled

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