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 SSU 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 SSU is None
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
I need a better understading onn solving thi question?
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 4 images
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education