Python binary search always returns target not found value

Question

I've written the following code to do a binary search for a value, target, in a list or tuple, collection.

def binary(collection, target):
    """Binary search
    Takes a sorted list or tuple, collection, then searches for target
    Returns -1 if item isn't found. """
    length = len(collection)
    minimum = 0
    maximum = length - 1
    while minimum <= maximum:
        pivot = (minimum + maximum) // 2
        if collection[pivot] is target:
            return pivot
        elif collection[pivot] > target:
            minimum = pivot + 1
        else:
            maximum = pivot - 1
    return -1

As you can see, when target isn't found in collection, the function returns -1. No matter what I've done, the function has returned -1.

>>> test = [1, 2, 3, 4, 5, 6]
>>> binary(test, 5)
-1
>>> binary(test, 1)
-1

What's causing this problem?

Answer 1

You have this condition backwards:

elif collection[pivot] > target:

Switch it and the search works:

elif collection[pivot] < target:

For what it's worth, I figured this out by adding a printout to your search to see what's happening. When in doubt, add a printout:

>>> binary([1, 2, 3], 1)
(min=0, max=2, pivot=1)
(min=2, max=2, pivot=2)
     ^ Oops

# After fixing...
>>> binary([1, 2, 3], 1)
(min=0, max=2, pivot=1)
(min=0, max=0, pivot=0)

By the way, the built-in bisect module performs binary searches. You don't have to write your own, unless you're doing it for educational value.