Week 7 - Searching Lists

Outcomes

You should be able to:

• Describe the algorithm for a linear search
• Describe the algorithm for a binary search
• Recognize/identify the code for a linear or binary search.
• Identify the Big-oh runtime analysis for a linear or binary search.
• Explain where O(log n) fits into the "rankings" of O(1), O(n) and O(n^2)
• Read existing Python code and connect it to corresponding pseudocode [We begin the process and continue over the next few weeks]

Activities

• TASK 1 - Write a function called extractCities() that generates a list of all of the cities provided in the given data file
  • IA_population_data.txt [Data file]
• Note, this should be at a skill level you had in FOP.

• TASK #2 - Write a function called lookFor() that:
  • takes in a list of cities (like the one generated by extractCities())
  • and the name of a city
  • returns True or False depending on whether this city is in the list

 




• TASK #3 - Given the pseudocode we wrote together in class, write lookForBinary() that:
  • takes in a list of cities (like the one generated by extractCities())
  • and the name of a city
  • returns True or False depending on whether this city is in the list
  • BUT, does so using a binary search process