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: For now, print out the values of these 3 variables, and then answer Question 7. Once you have completed Question 10, 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: Answer Question 11 in your writeup.
  7. Based on your answer to Question 11, 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 11, 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 12-15 in your writeup.
  12. Demo your program.
  13. Continue to Part D.