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?

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky — Professor Donald Knuth. — FMc
– FMc, Commented Sep 11, 2010 at 12:21
Is there any topic that Donald Knuth doesn't have a quote on? — Rafe Kettler
– Rafe Kettler, Commented Sep 11, 2010 at 14:15

John Kugelman · Accepted Answer · 2010-09-11 05:27:54Z

4

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.

edited Sep 11, 2010 at 5:27

answered Sep 11, 2010 at 5:22

John Kugelman

364k70 gold badges555 silver badges600 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Rafe Kettler Over a year ago

Educational value, purely. I sort of banged it out based on what I remembered a binary search to be.

Rafe Kettler Over a year ago

I took a look at the bisect module and it seems that bisect_left() can work as a binary search with slight modification. Thanks for the tip.

John Kugelman Over a year ago

The last time I tried to write my own binary search it took me around 10 iterations to get the stupid thing working. Off-by-one errors are my kryptonite. :-)

Rafe Kettler Over a year ago

While we're talking binary search, would it be better to raise a ValueError rather than return -1 if the value isn't found? I feel like if someone used this and didn't read the source or docstring, they'd feed it into a list index and get an index when the value wasn't found (since -1 is a valid index)

John Kugelman Over a year ago

Even the Python library can't make up its mind: str.find returns -1, str.index raises ValueError. Although list only has index, so maybe that breaks the tie.

|

pjkundert · Accepted Answer · 2011-02-16 20:01:12Z

1

In addition to correcting your condition test to elif collection[pivot] < target: , you used the "is" operator for testing whether you have found your target item:

    if collection[pivot] is target:

You should use "==" instead:

    if collection[pivot] == target:

Using "is" tests whether two things are actually the same object. In Python, quite often small string and integer objects turn out to be stored and recycled, so this might work. However, in most cases, it will not:

>>> a='abc'
>>> id(a)
2129839392
>>> b='ab'
>>> b+='c'
>>> id(b)
2129963136
>>> a
'abc'
>>> b
'abc'
>>> binary([a],a)
0
>>> binary([a],b)
-1

answered Feb 16, 2011 at 20:01

pjkundert

4894 silver badges8 bronze badges

Collectives™ on Stack Overflow

Python binary search always returns target not found value

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related