- 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
- 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.
- Write a def line for this new binary_search_recursive function.
Include a useful docstring.
The parameters of this function are:
- The list to search (which must already be sorted)
- The value to search for
- The first index where the value could be
- The last index where the value could be
If the value to search for is in the list, this function will eventually return its index.
Otherwise, this function will return None.
- 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
- 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.
- 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
- 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.
- 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.
- Answer Question 7 in your writeup.
- 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
- Answer Question 8 in your writeup.
- When your code is correct, call an instructor to demo.
- Make sure your docstring reflects your updates to the code.
- Continue to Part C to submit your code.