Python Search Algorithm Timing Compare the predicted and actual run times of you
ID: 3886312 • Letter: P
Question
Python
Search Algorithm Timing
Compare the predicted and actual run times of your sequential search, your binary search, and python’s built-in search.
You can assume python’s built-in search is linear, O(n). Create tables and graphs of your timing data and predictions. The list class index method uses python’s built in search to give the index of a certain value.
ind = my_list.index( value )
This method will crash or raise an exception if it does not find the value sought. You can handle the exception with try/except. However, there is a simpler way to time python search’s worst case behavior. Looking for a value not in the list takes n comparisons. So does looking for the biggest value in a sorted list. That value will be found and will not cause a crash. Just make a list of the values 1 through n and search for n to get worst case behavior. Do all searching on SORTED lists. Sequential and python search work on unsorted data but just use sorted data for all timing. Do all timing for all algorithms on the same computer. To get an accurate timing of something fast, remember that you can increase n (make a larger list) and/or you can do the search k times, then divide the time by k to get an individual search time.
Explanation / Answer
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos = pos+1
return found
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.