Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

The binary_search function returns the position of key in the list if found, or -1 if not found. We want to make sure that it's

The binary_search function returns the position of key in the list if found, or -1 if not found. We want to make sure that it's working correctly, so we need to place debugging lines to let us know each time that the list is cut in half, whether we're on the left or the right. Nothing needs to be printed when the key has been located.

For example, binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3) first determines that the key, 3, is in the left half of the list, and prints "Checking the left side", then determines that it's in the right half of the new list and prints "Checking the right side", before returning the value of 2, which is the position of the key in the list.

Add commands to the code, to print out "Checking the left side" or "Checking the right side", in the appropriate places.

def binary_search(list, key):
#Returns the position of key in the list if found, -1 otherwise.

#List must be sorted:
list.sort()
left = 0
right = len(list) - 1

while left <= right:
middle = (left + right) // 2

if list[middle] == key:
return middle
if list[middle] > key:
right = middle - 1
if list[middle] < key:
left = middle + 1
return -1

print(binary_search([10, 2, 9, 6, 7, 1, 5, 3, 4, 8], 1))
"""Should print 2 debug lines and the return value:
Checking the left side
Checking the left side
0
"""

print(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))
"""Should print no debug lines, as it's located immediately:
4
"""

print(binary_search([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], 7))
"""Should print 3 debug lines and the return value:
Checking the right side
Checking the left side
Checking the right side
6
"""

print(binary_search([1, 3, 5, 7, 9, 10, 2, 4, 6, 8], 10))
"""Should print 3 debug lines and the return value:
Checking the right side
Checking the right side
Checking the right side
9
"""

print(binary_search([5, 1, 8, 2, 4, 10, 7, 6, 3, 9], 11))
"""Should print 4 debug lines and the "not found" value of -1:
Checking the right side
Checking the right side
Checking the right side
Checking the right side
-1
"""

Step by Step Solution

3.38 Rating (157 Votes )

There are 3 Steps involved in it

Step: 1

def binarysearchlist key Returns the position of key in the list if found 1 otherwise List must be s... blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Operations And Supply Chain Management

Authors: F. Robert Jacobs, Richard Chase

14th Edition

978-0077824921, 78024021, 9780077823344, 007782492X, 77823346, 978-0078024023

More Books

Students also viewed these Business Communication questions

Question

Write a program to check an input year is leap or not.

Answered: 1 week ago

Question

Write short notes on departmentation.

Answered: 1 week ago

Question

What are the factors affecting organisation structure?

Answered: 1 week ago

Question

What are the features of Management?

Answered: 1 week ago

Question

Briefly explain the advantages of 'Management by Objectives'

Answered: 1 week ago