CODEWITHSUNDEEP
pythonalgorithmsearchbinarybinary-search
Cipher
Cipher

Reputation: 91

Binary Search Function

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

Upvotes: 0

Views: 1320

Answers (3)

greeness
greeness

Reputation: 16104

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

Upvotes: 1

lynxlynxlynx
lynxlynxlynx

Reputation: 1433

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.

Upvotes: 1

Matt
Matt

Reputation: 3353

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.

Upvotes: 1

Related Questions