CODEWITHSUNDEEP
pythonrecursion
fin1234
fin1234

Reputation: 9

Binary Search recursive implementation

I am trying to create the implementation of a recursive version of my binary search. This is what I have so far. Can anyone help I am not sure how to finish.

def binarySearch(searchList, numberSought, low, high):
    if high < low:
        return False
    midpoint = (low + high)//2
    print ("high is index", high)
    print ("low is index", low)
    print ("midpoint is index", midpoint)
    if searchList[midpoint] == numberSought:
        return True
    elif ...

    else:
        ...

mylist = [2, 4, 7, 13, 21, 22, 27, 31, 41, 77, 97, 144, 168]
first = 0
last = len(mylist) - 1
candidate = int(input("Does our list contain the following number? "))
print ("It is ",binarySearch(mylist,candidate,first,last), "that our list contains", candidate)

Upvotes: 0

Views: 875

Answers (3)

user2623906
user2623906

Reputation:

you can use this recursive program.. to perform Binary Search. 

>>>def BS(list,key,min,max):
    if max<min:
        return None
    else:
        mid=(min+(max-min)/2)
    if list[mid]>key:
        return BS(list,keyey,min,mid-1)
    elif list[mid]<key:
        return BS(list,key,mid+1,max)
    else:
        return mid

>>> min = 0
>>> list = [2, 4, 7, 13, 21, 22, 27, 31, 41, 77, 97, 144, 168]
>>> max = len(list)-1
>>> key = 21
>>> BS(list,key,min,max)

wiki says: a binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value.[1][2] In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned.

Upvotes: 0

sjakobi
sjakobi

Reputation: 3606

Why not look at the source code for the non-recursive but canonical implementation in the Python bisect module? You'd have to turn the while-loop into a recursion of course.

Upvotes: 0

Useless
Useless

Reputation: 67713

Your next step is to fill in these blanks:

    if searchList[midpoint] == numberSought:
        return True
    elif searchList[midpoint] < numberSought:
        pass # somehow search left of midpoint here
    else: # must have > numberSought
        pass # somehow search right of midpoint here

Does that help?

Upvotes: 2

Related Questions