The 365 Data Science team is proud to invite you to our own community forum. A very well built system to support your queries, questions and give the chance to show your knowledge and help others in their path of becoming Data Science specialists.
Ask
Anybody can ask a question
Answer
Anybody can answer
Vote
The best answers are voted up and moderated by our team

Python Programmer Bootcamp: Binary Search. Possible error?

Python Programmer Bootcamp: Binary Search. Possible error?

0
Votes
1
Answer

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:

  1. 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.
  2. 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.
  3. 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
1 Answer

365 Team
0
Votes

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 
 

Oh ok, thanks for your tips Eli!

2 weeks