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

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
icon
Related questions
Question

With the code given can you solve this question 

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
Transcribed Image Text: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
1 def linear_search(search_list, value_to_find):
2
3
for i, item in enumerate(search_list):
if item == value_to_find:
return i
4
5
7
8
9
10
def readfile(filename):
with open(filename, "r") as file:
file.readlines ()
12
13
14
15 if
16
17
18
19
20
21
22
23
24
25
26
27
28
29
lines
return lines
def
print_list(list_to_print):
for i, item in enumerate(list_to_print):
print(i, ": ",item, sep="")
name
filename
"1
input()
file_contents = readfile(filename)
file_contents = [line.rstrip() for line in file_contents]
print("Number of lines in file:", len(file_contents))
print_list(file_contents)
else:
main":
=
city=input()
position
if position is not None:
print("\n(Linear Search) The position of", city, "is", position)
print("\n(Linear Search) The position of", city, "is None")|
linear_search(file_contents, city)
Transcribed Image Text:1 def linear_search(search_list, value_to_find): 2 3 for i, item in enumerate(search_list): if item == value_to_find: return i 4 5 7 8 9 10 def readfile(filename): with open(filename, "r") as file: file.readlines () 12 13 14 15 if 16 17 18 19 20 21 22 23 24 25 26 27 28 29 lines return lines def print_list(list_to_print): for i, item in enumerate(list_to_print): print(i, ": ",item, sep="") name filename "1 input() file_contents = readfile(filename) file_contents = [line.rstrip() for line in file_contents] print("Number of lines in file:", len(file_contents)) print_list(file_contents) else: main": = city=input() position if position is not None: print("\n(Linear Search) The position of", city, "is", position) print("\n(Linear Search) The position of", city, "is None")| linear_search(file_contents, city)
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 8 steps with 4 images

Blurred answer
Knowledge Booster
Array
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
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)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education