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

• Watch - Getting Started by extracing cities [Video, 5 minutes]
  • IA_population_data.txt [Data file]


• [Optional task, #1] - Write a function called extractCities() that generates a list of all of the cities provided in the given data file
  • Explained in the previous video
• Note, this should be at a skill level you had in FOP.
• Everyone SHOULD be able to do this.
• Your ability to write code is not graded in this course. But I think this activity is a good review and keeps your skills moving.


• Schafer's Solution to task #1
  • solution1.py [code]
  • Watch - I explain my code [Video, 3 minutes]


• Watch - Suppose I want to find if a city was in my data set... [Video, 3 minutes]


• [Optional 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
  • AGAIN, you should all be able to do this. This is not complex code and we have largely looked at this code in previous weeks when studying Big-Oh notation.


• Schafer's Solution to task #2
  • solution2.py [code]
  • Watch - I explain my code [Video, 4 minutes]


• Watch - That solution was easy. But it isn't necessarily the way we would do it in real life [Video, 9 minutes]


• Watch - The pseudocode for a binary search [Video, 10 minutes]


• [Optional task, #3] - Given the pseudocode we wrote in the previous video, 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


• Schafer's Solution to task #3
  • solution3.py [code]
  • Watch - I explain my code [Video, 13 minutes]
  • Watch - Except there is an "error" [Video, 9 minutes]
  • solution3Improved.py [code]


• Now that you have worked through all of this material, let's connect it back to the readings in the book
  • NOTE: we are skipping chapter 4 for now. I don't want to address this until we have the right context.
  • Read Section 5.2
  • Read Section 5.3
  • Read Section 5.4
    • Note, you should not worry about the CodeLens code labeled
    • 
    • This uses the technique from chapter 4 that we won't study until next week.


• Finally, let's talk about the Big-Oh (Omega) notation for these two searches
  • NOTICE: This introduces a new , Big-Oh value
• Watch - Binary vs. Linear - Conceptually [Video, 14 minutes]
• Watch - Binary vs. Linear - Benchmark (timing the code) [Video, 10 minutes]
• Code from your book
  • linear_search_code.py
  • binary_search_code.py
• My Timer Code
  • search_with_timeit.py