The binary_search function returns the position of key in

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
“””