Binary Search recursive implementation

Question

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)

Answer 1

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?

• fin1234: if lo < 0: 13 raise ValueError('lo must be non-negative') 14 if hi is None: 15 hi = len(a) 16 while lo < hi: 17 mid = (lo+hi)//2 18 if x < a[mid]: hi = mid 19 else: lo = mid+1 20 a.insert(lo, x) 21 22 insort = insort_right would this be the correct idea?(taken form below)
• Useless: For a recursive implementation, each pass statement should be replaced by another call to binarySearch ...

Answer 2

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.

• fin1234: so this would be the correct source to base mine of off? if lo < 0: 13 raise ValueError('lo must be non-negative') 14 if hi is None: 15 hi = len(a) 16 while lo < hi: 17 mid = (lo+hi)//2 18 if x < a[mid]: hi = mid 19 else: lo = mid+1 20 a.insert(lo, x) 21 22 insort = insort_right
• Hans Then: But probably not recursive.
• sjakobi: @HansThen: Gosh, how couldn't I see that he was looking for a recursive solution...

Answer 3

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.