14,880,436 members
1.00/5 (1 vote)
See more:
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:

Python
```<pre>def linear_search(list, key):
#Returns the number of steps to determine if key is in the list

#Initialize the counter of steps
steps=0
for i, item in enumerate(list):
steps += 1
if item == key:
break
return ___

def binary_search(list, key):
#Returns the number of steps to determine if key is in the list

#List must be sorted:
list.sort()

#The Sort was 1 step, so initialize the counter of steps to 1
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))
#Should be: Linear: 1 steps, Binary: 4 steps. Best Search is Linear.

print(best_search([10, 2, 9, 1, 7, 5, 3, 4, 6, 8], 1))
#Should be: Linear: 4 steps, Binary: 4 steps. Result is a Tie.

print(best_search([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], 7))
#Should be: Linear: 4 steps, Binary: 5 steps. Best Search is Linear.

print(best_search([1, 3, 5, 7, 9, 10, 2, 4, 6, 8], 10))
#Should be: Linear: 6 steps, Binary: 5 steps. Best Search is Binary.

print(best_search([5, 1, 8, 2, 4, 10, 7, 6, 3, 9], 11))
#Should be: Linear: 10 steps, Binary: 5 steps. Best Search is Binary.```
Posted
Updated 16-Nov-20 21:18pm
v2

Just a quick note: If your binary search performs a sorting (O(N logN)) and then performs a binary search (O(logN)) then I can tell you roughly that linear search will perform fewer operations (O(N)).

Regardless of input, your binary search will be doing a sort.
Chiranthaka Sampath 16-Nov-20 1:54am

From your point of view, what am I missing here?

I have expanded over my comment in the answer, see Solution 1.

## Solution 1

If we talk about a "step", then you are not missing rather adding a few steps. :laugh:

If we talk about the "point", then you missed the point of counting the "overall" steps needed by each method. The goal of a binary search is to find elements in O(logN) but it requires the data to be sorted to work; otherwise, it doesn't guarantee correct output.

If you end up sorting the array for each search operation, then you end up adding an extra O(N logN) for sorting, for each search. This leads to extra steps in binary search and leading to the incorrect notion that binary search takes extra steps.

I hope this helps you understand what I am trying to say.

There are two things that you can do here:

1. Sort the data
1. Do not sort the data (and do not add the `list.sort` either)

But, if you sort the data then binary search is at a huge advantage over a linear search.

If you do not sort the data, then they are both are a random chance with linear search being more accurate and binary search leading to incorrect results at times.
I said it:
Oh, and a quick point, do not name your variables/parameters to list, set or map, which are Python method names. Doing this will lead to problems when you want to create a new list or a map, because Python will continue using your variable and hide the underlying Python keywords.