CS 115 Lab 10, Part C: Binary search

[Back to lab instructions]

Instructions

1. Make a copy of your lab10b.py file. Name it lab10c.py.

2. Binary search only works if the input list is sorted. Currently, our lists are not sorted.

   In main, after printing the list of cities, add another line of code to sort the list:

   city_list.sort()  # use the name of your list in place of city_list

   Then print the sorted version of the list.

   Sample input and 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
   The position of Petaluma is:
   Linear search: 1
   
   Enter the name of a city: Windsor
   The position of Windsor is:
   Linear search: 4
   
   Enter the name of a city: Cotati
   The position of Cotati is:
   Linear search: None
   
   Enter the name of a city: quit

3. Add the following function definition to your program:

   def binary_search(search_list, value_to_find):
       """
       Uses a binary search function to find the position of an item in a list
       Parameters: the list; the item to search for
       Returns: the position of the item in the list
                (or None if it is not in the list)
       """
       pass

4. In main, call binary_search inside your loop after calling linear search. Sample 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: Petaluma
   The position of Petaluma is:
   Linear search: 1
   Binary search: None
   
   Enter the name of a city: Windsor
   The position of Windsor is:
   Linear search: 4
   Binary search: None
   
   Enter the name of a city: Cotati
   The position of Cotati is:
   Linear search: None
   Binary search: None
   
   Enter the name of a city: quit

5. Inside the definition of binary_search, create three variables:
   • first -- this should be equal to the index of the first element in the list that was passed to binary_search
   • last -- this should be equal to the index of the last element in the list that was passed to binary_search
   • middle -- this should be equal to the index of the middle element in the list that was passed to binary_search. If there is an even number of elements, middle should be rounded down so that it refers to the earlier of the two middle elements. Be sure to use a formula that will be correct as long as first is less than or equal to last.
   For now, print out the values of these 3 variables, and then answer Question 7. Once you have completed Question 7, comment out these print statements.
6. Inside binary_search, add a while loop. For now, make the condition while True: Inside this loop, add code to do the following:
   • Calculate middle (move the line of code for middle from the previous step inside the loop).
   • Return middle if value_to_find is equal to the middle element of the list.
   • Adjust first if value_to_find comes after the middle element of the list.
   • Adjust last if value_to_find comes before the middle element of the list.
   Answer Question 8 in your writeup.
7. Based on your answer to Question 8, modify your while loop so that the loop ends if the positions of first and last indicate that value_to_find is not in the list.
8. Rerun your program on all of the sample inputs from Question 8, and be sure that it always returns the correct position without infinite looping.
9. Inside the definition of binary_search, add code to your while loop to count the number of loop iterations. Print the value of this counter just before you return from the function. (Because your function can return from two different places, you will need to insert two print statements.)
10. Edit your program until you 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: Windsor
    Linear search: 4
    **Binary search iterations: 3
    Binary search: 4
    
    Enter the name of a city: Rohnert Park
    Linear search: 2
    **Binary search iterations: 1
    Binary search: 2
    
    Enter the name of a city: SSU
    Linear search: None
    **Binary search iterations: 2
    Binary search: None
    
    Enter the name of a city: quit

11. Test your code on the larger cities.txt file, and answer Questions 9-12 in your writeup.
12. Demo your program.
13. Continue to Part D.