CODEWITHSUNDEEP
pythonpython-2.7
user856358
user856358

Reputation: 593

Implementing a binary search

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?

Upvotes: 1

Views: 101

Answers (1)

jwodder
jwodder

Reputation: 57460

Two problems:

  1. When you recurse by calling bisect, you still need to return the value of the call by doing return bisect(list[:split],target).

  2. 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:].

Upvotes: 4

Related Questions