Title

Traveling Merchant Problem Hacks:

What did you and your team discuss? (record below)

• An __ solution is __ that produces a solution that isn't necessarily _ but can be used when normal methods take forever

Describe the method used to solve the traveling merchant problem. (record below)

import time

def linear_search(lst, x):
    start_time = time.perf_counter_ns() # records time (nanoseconds)
    for i in range(len(lst)): # loops through the entire list 
        if lst[i] == x: # until the x value we are looking for is found
            end_time = time.perf_counter_ns() # records time again
            total_time = (end_time - start_time) // 1000 # subtracts last recorded time and first recorded time
            print("Found element after {} loops in {} microseconds".format(i+1, total_time)) # prints the results
            return print("Your number was found at", i)
    end_time = time.perf_counter_ns() # records the time again
    total_time = (end_time - start_time) // 1000 # subtracts last recorded time and first recorded time
    print("Element not found after {} loops in {} microseconds".format(len(lst), total_time)) # prints the results
    return "Your number wasn't found :("

lst = list(range(1, 10001)) # list with numbers 1-10000
x = 5000 # replace with an integer between 1 and 10000 (I suggest big numbers like 500, 2000, so on)
linear_search(lst, x) # runs procedure

import time 

def binary_search(lt, x):
    start_time = time.perf_counter_ns() # starts timer
    low = 0 # sets the lower side 
    mid = 0 # sets mid value
    high = len(lt) -1 # sets the higher side
    num_loops = 0 # number of loops the search undergoes to find the x value

    while low<=high: # Loop ran until mid is reached
        num_loops += 1 # adds one loop each time process is repeated
        mid = (low + high) // 2 # takes the lowest and highest possible numbers and divides by 2 and rounds to closest whole #
        if lt[mid] == x:
            end_time = time.perf_counter_ns() # records time
            total_time = (end_time - start_time) // 1000 # time in microseconds
            print("Element found after {} loops in {} microseconds".format(num_loops, total_time)) # prints the results
            return mid # returns the index value
        elif lt[mid] > x: # if mid was higher than x value, then sets new highest value as mid -1 
            high = mid -1 
        elif lt[mid] < x:
            low = mid + 1 # if mid was lower than x, sets the new low as mid + 1
    end_time = time.perf_counter_ns()
    total_time = (end_time - start_time) // 1000 
    print("Element not found after {} loops in {} microseconds".format(num_loops, total_time)) # prints the results
    return "Your number wasn't found :("

lt = list(range(1, 10001)) # list with numbers 1-10000
x = 149 # replace with an integer between 1 and 10000 (I suggest big numbers like 500, 2000, so on)
binary_search(lt, x) # runs procedure