9.23 City Search (Part C, Binary Search) In this part, we will extend our code to also implement binary search. Prepare the list Binary search only works if the input list is sorted. Currently, our lists are not sorted. After printing the list of cities, use the sort() method to sort the list and then print the sorted list. When the file is cities-small.txt and the city is Rohnert Park, your enhanced program should have the below output: Number of lines in file: 5 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 (Linear Search) The position of Rohnert Park is 2 Implement binary_search 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. Args: search_list (list): The list. value_to_find (str): The item to search for. Returns: int: The position of the item in the list, or None if it is not in the list. pass You may use the code provided in Figure 10.2.1 to implement this function. Make sure you understand all the variables involved. Also, note that the above function returns None if the value_to_find is not found in the search_list. 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.) Complete main In main, after calling your linear search function, add code to do the following: • Call your binary search function to get the position of the city entered by the user. • Print the result. Sample Input/Output Sample output when the file provided is cities-small.txt and the city provided is Rohnert Park Number of lines in file: 5 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 (Linear Search) The position of Rohnert Park is 2 **Binary search iterations: 1 (Binary Search) The position of Rohnert Park is 2 Sample output when the file provided is cities-small.txt and the city provided is SSU Number of lines in file: 5 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 (Linear Search) The position of SSU is None **Binary search iterations: 2 (Binary Search) The position of SSII is None

9.23 City Search (Part C, Binary Search) In this part, we will extend our code to also implement binary search. Prepare the list Binary search only works if the input list is sorted. Currently, our lists are not sorted. After printing the list of cities, use the sort() method to sort the list and then print the sorted list. When the file is cities-small.txt and the city is Rohnert Park, your enhanced program should have the below output: Number of lines in file: 5 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 (Linear Search) The position of Rohnert Park is 2 Implement binary_search 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. Args: search_list (list): The list. value_to_find (str): The item to search for. Returns: int: The position of the item in the list, or None if it is not in the list. pass You may use the code provided in Figure 10.2.1 to implement this function. Make sure you understand all the variables involved. Also, note that the above function returns None if the value_to_find is not found in the search_list. 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.) Complete main In main, after calling your linear search function, add code to do the following: • Call your binary search function to get the position of the city entered by the user. • Print the result. Sample Input/Output Sample output when the file provided is cities-small.txt and the city provided is Rohnert Park Number of lines in file: 5 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 (Linear Search) The position of Rohnert Park is 2 Binary search iterations: 1 (Binary Search) The position of Rohnert Park is 2 Sample output when the file provided is cities-small.txt and the city provided is SSU Number of lines in file: 5 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 (Linear Search) The position of SSU is None **Binary search iterations: 2 (Binary Search) The position of SSII is None

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter17: Linked Lists

Section: Chapter Questions

Problem 16PE

See similar textbooks