Modify the findLocation function so that it uses a binary search instead of a se

Question

Modify the findLocation function so that it uses a binary search instead of a sequential search.  It should still have the following skeleton:

def findLocationBinary(yearList, locList, year):

     # Fill in the code to find the year

     # in the year list and return the

     # associated location from the location list

return location

But the algorithm that you use to find the year should be binary search.  You can find the code for binary search below.  It will need to be modified slightly to fit this problem.

You can find the olympics.py file here:

https://www.dropbox.com/s/ro8yn485x9sj27b/olympics.py

and the olympics.txt file here:

https://www.dropbox.com/s/cetvm9b5a9hy3sl/Olympics.txt

Explanation / Answer

def findLocation(yearList, locList, year):

lo = 0

hi = len(yearList)

while lo < hi:

mid = (lo+hi)//2

midval = yearList[mid]

if midval < year:

lo = mid+1

elif midval > year:

hi = mid

else:

return locList[mid]

return -1

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.