Click here to Skip to main content
14,880,436 members
Please Sign up or sign in to vote.
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
Comments
Afzaal Ahmad Zeeshan 15-Nov-20 14:39pm
   
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?
Afzaal Ahmad Zeeshan 17-Nov-20 3:18am
   
I have expanded over my comment in the answer, see Solution 1.

1 solution

Continuing from the comments.

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.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900