Binary Search Function

Question

Good evening. I am trying to get back in to programming and have decided to do some practice coding on my own time. I'm currently trying to implement a binary search but there appears to be a continuous loop in my code. Could someone give me a hint as to what is going on?

def binChop(key, ordered_set):
 found = False
 newSet = ordered_set
 while found != True or newSet > 0:
 midpoint = int(len(newSet)/2)
 if key < newSet[midpoint]:
 found = False
 newSet = newSet[:midpoint]
 elif key > newSet[midpoint]:
 found = False
 newSet = newSet[midpoint:]
 elif key==newSet[midpoint]:
 found = True
 return found

• mgibsonbr: There's no valid exit condition if the set is reduced to a single element (or zero elements) and the search key is not found. (Edit: unless newSet > 0 actually checks whether len(newSet) > 0; what is the type of ordered_set?)
• Cipher: That was an error from the number of different edits I've done. Thanks for catching it but it still hits an endless loop somewhere :(

Answer 1

I think your problem is in the condition for the while loop. You have an 'or' rather than an 'and' - this means that even if you find your result, the newSet>0 condition will be satisfied.

• Cipher: That seems to have worked. Unfortunately I can't get it to return False if a number isn't in the set. Just loops. That should narrow it down for me though. Thank you for the help.

Answer 2

I suspect "newSet> 0" is always true. If it was a standard python set, you would get an error:

>>> b=set()
>>> b
set([])
>>> b > 0
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
TypeError: can only compare to a set

But since you don't, I guess it's a list or tuple:

>>> a=[]
>>> a > 0
True
>>> b=()
>>> b > 0
True

Which both don't do what you expect (checking for length).

In general, add import pdb; pdb.set_trace() to the code and step through it to find a bug.

• Cipher: Awesome. Thanks for the heads up. That will come in handy

Answer 3

You have a few issues and some that can be improved :

• You need the left and right boundary index to correctly perform binary search when the element is not in the ordered list. See the correct algorithm here. You get out of the while loop when you either find your key or the left boundary is on the right of the right boundary or vice versa (max_point < min_point).
• You don't need the newSet. You can always use an index into the sorted list. So the mid_point is just an index, so do min_point (the left boundary) and max_point (the right boundary).
• A binary search usually returns the index of key as return. If not found, return -1.

My python code is shown as below:

def binChop(key, ordered_list):
 min_point, max_point = 0, len(ordered_list)-1
 while min_point <= max_point:
 mid_point = (min_point+max_point)/2
 if ordered_list[mid_point] < key:
 min_point += 1
 elif ordered_list[mid_point] > key:
 max_point -= 1
 else:
 return mid_point
 return -1
test_cases = [[], [5], [4,5], [5,6], [1,5,6], [1], [1,4], [1,6,15]]
for ordered_list in test_cases:
 print "%-10s %5s" % (ordered_list, binChop(5, ordered_list))

---

Outputs:
list index of 5
[] -1
[5] 0
[4, 5] 1
[5, 6] 0
[1, 5, 6] 1
[1] -1
[1, 4] -1
[1, 6, 15] -1