21.14 LAB: Binary Search Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an argument. Complete the recursive function binary_search() with the following specifications: 1. Parameters: o a list of integers o a target integer o lower and upper bounds within which the recursive call will search 2. Return value: o if found, the index within the list where the target is located o 1 if target is not found The algorithm begins by choosing an index midway between the lower and upper bounds. 1. If target nums[index] return index 2. If lower -- upper, return lower if target -- nums [lower] else -1 to indicate not found 3. Otherwise call the function recursively with half the list as an argument: o If nums [index] < target, search the list from index to upper o if nums [index] > target, search the list from lower to index The list must be ordered, but duplicates are allowed. Once the search algorithm works correctly, add the following to binary_search(): 4. Count the number of calls to binary_search(). anamMvee Đaymber of times when the target is ompared to an element of the list. Note: lower == upper should not be counted. Hint: Use a global variable to count calls and comparisons. The Input of the program consists of integers on one line followed by a target integer on the second. The template provides the main program and a helper function that reads a list from input. Ex: If the input is: 1 234 5 6789 the output is: recurs ions: comparisons: 3
21.14 LAB: Binary Search Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an argument. Complete the recursive function binary_search() with the following specifications: 1. Parameters: o a list of integers o a target integer o lower and upper bounds within which the recursive call will search 2. Return value: o if found, the index within the list where the target is located o 1 if target is not found The algorithm begins by choosing an index midway between the lower and upper bounds. 1. If target nums[index] return index 2. If lower -- upper, return lower if target -- nums [lower] else -1 to indicate not found 3. Otherwise call the function recursively with half the list as an argument: o If nums [index] < target, search the list from index to upper o if nums [index] > target, search the list from lower to index The list must be ordered, but duplicates are allowed. Once the search algorithm works correctly, add the following to binary_search(): 4. Count the number of calls to binary_search(). anamMvee Đaymber of times when the target is ompared to an element of the list. Note: lower == upper should not be counted. Hint: Use a global variable to count calls and comparisons. The Input of the program consists of integers on one line followed by a target integer on the second. The template provides the main program and a helper function that reads a list from input. Ex: If the input is: 1 234 5 6789 the output is: recurs ions: comparisons: 3
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Python
![21.14 LAB: Binary Search
Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an
argument.
Complete the recursive function binary_search() with the following specifications:
1. Parameters:
o a list of integers
o a target integer
o lower and upper bounds within which the recursive call will search
2. Return value:
o if found, the index within the list where the target is located
o -1 if target is not found
The algorithm begins by choosing an index midway between the lower and upper bounds.
1. If target == nums[index] return index
2. If lower == upper, return lower if target == nums[lower] else -1 to indicate not found
3. Otherwise call the function recursively with half the list as an argument:
o If nums [index] < target, search the list from index to upper
o If nums [index] > target, search the list from lower to index
The list must be ordered, but duplicates are allowed.
Once the search algorithm works correctly, add the following to binary_search():
4. Count the number of calls to binary_search().
5 Count the number of times when the target is compared to an element of the list. Note: lower -- upper should not be counted
Hint: Use a global variable to count calls and comparisons.
The Input of the program consists of integers on one line followed by a target integer on the second.
The template provides the main program and a helper function that reads a list from input.
Ex: If the input is:
1 2 3 4 5 6789
the output is:
index: 1,
recursions: 2, comparisons: 3](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F6046cbb1-e308-4521-9255-72f2b16e119a%2Ffa436d79-8315-40b6-9c5d-3ad424f1da91%2Fhkqcb76_processed.jpeg&w=3840&q=75)
Transcribed Image Text:21.14 LAB: Binary Search
Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an
argument.
Complete the recursive function binary_search() with the following specifications:
1. Parameters:
o a list of integers
o a target integer
o lower and upper bounds within which the recursive call will search
2. Return value:
o if found, the index within the list where the target is located
o -1 if target is not found
The algorithm begins by choosing an index midway between the lower and upper bounds.
1. If target == nums[index] return index
2. If lower == upper, return lower if target == nums[lower] else -1 to indicate not found
3. Otherwise call the function recursively with half the list as an argument:
o If nums [index] < target, search the list from index to upper
o If nums [index] > target, search the list from lower to index
The list must be ordered, but duplicates are allowed.
Once the search algorithm works correctly, add the following to binary_search():
4. Count the number of calls to binary_search().
5 Count the number of times when the target is compared to an element of the list. Note: lower -- upper should not be counted
Hint: Use a global variable to count calls and comparisons.
The Input of the program consists of integers on one line followed by a target integer on the second.
The template provides the main program and a helper function that reads a list from input.
Ex: If the input is:
1 2 3 4 5 6789
the output is:
index: 1,
recursions: 2, comparisons: 3
![Load default template..
main.py
4 def binary_search(nums, target, lower, upper):
# Type your code here.
6
8 if
name
# Input a list of nums from the first Line of input
nums = [int(n) for n in input().split()]
main_':
==
10
11
# Input a target value
target = int(input())
12
13
14
# Start off with default values: full range of list indices
index = binary_search(nums, target, e, len(nums) 1)
15
16
17
# output the index where target was found in nums, and the
# number of recursions and comparisons performed
print(f'index: (index}, recursions: {recursions}, comparisons: {comparisons}")
18
19
20
21](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F6046cbb1-e308-4521-9255-72f2b16e119a%2Ffa436d79-8315-40b6-9c5d-3ad424f1da91%2Ft4o8lc9_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Load default template..
main.py
4 def binary_search(nums, target, lower, upper):
# Type your code here.
6
8 if
name
# Input a list of nums from the first Line of input
nums = [int(n) for n in input().split()]
main_':
==
10
11
# Input a target value
target = int(input())
12
13
14
# Start off with default values: full range of list indices
index = binary_search(nums, target, e, len(nums) 1)
15
16
17
# output the index where target was found in nums, and the
# number of recursions and comparisons performed
print(f'index: (index}, recursions: {recursions}, comparisons: {comparisons}")
18
19
20
21
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 3 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY