Python Programmer Bootcamp: Binary Search. Possible error?

Question

Hi, I want to thank you for such a complete and detailed course. I've learnt a lot of things. However, I would like to point out two things of the Binary Search lesson:

In the minute 8:47, the instructor is testing the binary_search function, but he uses linear_search. So I think that was a clear error.
The instructor says that in order to execute a binary search, the list must be sorted, and it makes sense. But the list he uses as an example was not sorted. I was not sure if I was understanding from that point. So, I tested a non-sorted list, and it didn't work.
After that, I added a line of code which sorts the given list from the beginning.

Please let me know whether I am correct or not. I have included the instructor's code, a test on his code, and my code. Thank you!

# Instructor's code

def binary_search(item,my_list):
    found = False
    first = 0
    last = len(my_list)-1
    
    while first <= last and found == False:
        midpoint = (first + last)//2
        if my_list[midpoint] == item:
            found = True
        else:
            if my_list[midpoint] < item:
                first = midpoint + 1
            else:
                last = midpoint - 1
    return found

# My list
test = [6,90,8,2,3,45,87,24,70]

# Testing instructor's code
# In: binary_search(90,test)
# Out: False


# My code adding a variable that containts the a given list but sorted.
# The list above returns true with this code.

def binary_search(item,my_list):
    sorted_list = sorted(my_list)
    found = False
    first = 0
    last = len(my_list)-1
    
    while first <= last and found == False:
        midpoint = (first + last)//2
        if sorted_list[midpoint] == item:
            found = True
        else:
            if sorted_list[midpoint] < item:
                first = midpoint + 1
            else:
                last = midpoint - 1
    return found

Answer 1

Hi Harold, thanks for reaching out and for the kind words! You're absolutely correct. The binary search algorithm requires a sorted array, otherwise it doesn't make sense to use the algorithm. First of all, your code works perfectly well and solves the problem at hand. However, we shouldn't perform the sorting in the binary search algorithm itself. Instead, we could sort the algorithm with a different function, and then apply the binary search. That's more to do with programming practices and the convention that binary search assumes that the array has been sorted already and starts from there. So, it's just better to split them into two separate functions, but of course the results are the same with both approaches. What you could add to the binary search algorithm is a check if the input array is sorted. And if it isn't you could print out a message saying "Binary search requires a sorted list" or something along those lines. Thanks so much for pointing out this error, we'll make sure to update the notebooks as soon as possible. Best, 365 Eli

Python Programmer Bootcamp: Binary Search. Possible error?

Submit an answer