Implementing a binary search

Question

I'm trying to implement a binary search; it takes an ordered list, takes the mid value, compares it to the target value, then sub-lists either above or below the mid value until the target is found or is missing from the list. However, for some reason, I always get 'None' returned unless the midpoint is the target. I'm not sure what's going wrong.

def bisect(list,target):


    print list
    split= list[len(list)//2]
    print "Split value : " + str(split)  

    if target==split: 
        return "target" 

    elif target<split:
        bisect(list[:split],target) 

    elif target>split:
        bisect(list[(split):],target)

a= [1,2,3,4,5,6,7,8,9,10]       
print bisect(a,2)

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Split value : 6
[1, 2, 3, 4, 5, 6]
Split value : 4
[1, 2, 3, 4]
Split value : 3
[1, 2, 3]
Split value : 2
None

It looks like the last compare between split and the target value isn't occurring?

@FredrikPihl or at least - look at how the bisect module implements its functions for comparison — Jon Clements
– Jon Clements, Commented May 10, 2013 at 19:15
As a side note: Calling your list list is confusing, and means you can't use the type/constructor of the same name within your function. — abarnert
– abarnert, Commented May 10, 2013 at 19:24
@abarnert true I'm not using the type so it's causing problems, but the way I did it is bad form. I will change it. — user856358
– user856358, Commented May 10, 2013 at 19:34

jwodder · Accepted Answer · 2013-05-10 19:17:42Z

4

Two problems:

When you recurse by calling bisect, you still need to return the value of the call by doing return bisect(list[:split],target).
split is an element of list, not an index, so list[:split] won't do what you think. Use list[:len(list)//2] instead, and likewise change list[split:] to list[len(list)//2:].

answered May 10, 2013 at 19:17

jwodder

58.1k12 gold badges116 silver badges134 bronze badges

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

2 Comments

abarnert Over a year ago

It would be nicer to do splitpoint = len(list)//2, then do split = list[splitpoint] and use list[:splitpoint] and list[splitpoint:], instead of repeating the same expression 3 times. But otherwise, great answer.

Janne Karila Over a year ago

@abarnert list[:splitpoint] and list[splitpoint+1:]. Omitting the +1 can lead to infinite recursion.

Collectives™ on Stack Overflow

Implementing a binary search

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related