CS 115 Lab 14, Part B: Sort City objects through Recursion

[Back to lab instructions]


Instructions

  1. This part builds on Lab 10, in which you built, sorted, and searched a list of cities. If you have not already done so, copy lab10c.py into the Lab14 directory and rename it to lab14b.py. Open lab14b.py. In main(), comment out the code where you call and print the result of linear search, and modify your print statements to match this sample output:
    Name of input file: cities-small.txt
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    
    After sorting, the new list is:
    0: Healdsburg
    1: Petaluma
    2: Rohnert Park
    3: Santa Rosa
    4: Windsor
    
    Enter the name of a city: Petaluma
    **Binary search iterations: 3
    The position of Petaluma is: 1
    
    Enter the name of a city: quit
  2. Go into the function definition for binary_search(). Right after you have calculated the initial values of first and last, add the following line of code:
    return binary_search_recursive(search_list, value_to_find, first, last)
    This will call a new, recursive binary search function that you are about to write, and return its result.
    Because this is a return statement, you won't end up executing anything in the function below this line. However, you should keep this code around for your reference.
  3. Write a def line for this new binary_search_recursive function.
    Include a useful docstring.
    The parameters of this function are: If the value to search for is in the list, this function will eventually return its index. Otherwise, this function will return None.
  4. Inside your new function, add a line of code that prints first and last. Here is an example of what your program should do so far:
    Name of input file: cities-small.txt
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    
    After sorting, the new list is:
    0: Healdsburg
    1: Petaluma
    2: Rohnert Park
    3: Santa Rosa
    4: Windsor
    
    Enter the name of a city: Petaluma
    Binary searching between 0 and 4
    The position of Petaluma is: None
    
    Enter the name of a city: quit
  5. Below the print statement, add a line of code that calculates the index of the middle element of the list. You can reuse the formula from the loop in your original binary search function.
  6. Add code that checks to see if the middle element of the list is the value that you're looking for. If it is, then you should return the index of the middle element.
    Sample input and output so far:
    Name of input file: cities-small.txt
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    
    After sorting, the new list is:
    0: Healdsburg
    1: Petaluma
    2: Rohnert Park
    3: Santa Rosa
    4: Windsor
    
    Enter the name of a city: Rohnert Park
    Binary searching between 0 and 4
    The position of Rohnert Park is: 2
    
    Enter the name of a city: Healdsburg
    Binary searching between 0 and 4
    The position of Healdsburg is: None
    
    Enter the name of a city: quit
  7. Copy (or rewrite) your code that adjusts first or last, based on whether the value you are looking for comes before or after the middle element.
  8. Rather than using a loop, you are going to have this function recursively call itself using your new values of first and last.
    At the very end of your function, include a return statement:
    return _______________________
    Fill in the blank with a call to binary_search_recursive that passes it the original list, the value to look for, and the new values of first and last.
  9. Answer Question 7 in your writeup.
  10. Finally, add a line to the beginning of your new function (just after the print statement) that will return None (or just return) if the values of first and last are unreasonable (that is, if first is actually after last). Sample output:
    Name of input file: cities-small.txt
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    
    After sorting, the new list is:
    0: Healdsburg
    1: Petaluma
    2: Rohnert Park
    3: Santa Rosa
    4: Windsor
    
    Enter the name of a city: San Francisco
    Binary searching between 0 and 4
    Binary searching between 3 and 4
    Binary searching between 3 and 2
    The position of San Francisco is: None
    
    Enter the name of a city: quit
  11. Answer Question 8 in your writeup.
  12. When your code is correct, call an instructor to demo.
  13. Make sure your docstring reflects your updates to the code.
  14. Continue to Part C to submit your code.