Hi All,
I have a question regarding a Python script that related with binary search. Please refer the below brief. The script has built with Python 3
Has 3 functions
1. linear_search()
2. binary_search()
3. best_search() - The best_search function compares linear_search and binary_search functions, to locate a key in the list, and returns how many steps each method took, and which one is the best for that situation.
The list does not need to be sorted, as the binary_search function sorts it before proceeding (and uses one step to do so). Here, linear_search and binary_search functions both return the number of steps that it took to either locate the key, or determine that it's not in the list.
If the number of steps is the same for both methods (including the extra step for sorting in binary_search), then the result is a tie.
I want to know what should I fill the blank spaces to get the correct answers.
What I have tried:
<pre>def linear_search(list, key):
steps=0
for i, item in enumerate(list):
steps += 1
if item == key:
break
return ___
def binary_search(list, key):
list.sort()
steps=1
left = 0
right = len(list) - 1
while left <= right:
steps += 1
middle = (left + right) // 2
if list[middle] == key:
break
if list[middle] > key:
right = middle - 1
if list[middle] < key:
left = middle + 1
return ___
def best_search(list, key):
steps_linear = ___
steps_binary = ___
results = "Linear: " + str(steps_linear) + " steps, "
results += "Binary: " + str(steps_binary) + " steps. "
if (___):
results += "Best Search is Linear."
elif (___):
results += "Best Search is Binary."
else:
results += "Result is a Tie."
return results
print(best_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 1))
print(best_search([10, 2, 9, 1, 7, 5, 3, 4, 6, 8], 1))
print(best_search([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], 7))
print(best_search([1, 3, 5, 7, 9, 10, 2, 4, 6, 8], 10))
print(best_search([5, 1, 8, 2, 4, 10, 7, 6, 3, 9], 11))