Past Problems
Recursion Problem - March 21st
The code below implements binary search iteratively. How should you modify the code to turn it into a recursive binary search?
Hints:
You may assume that the array is sorted (would it work if the array is not sorted?)
What would the base case be?
If the middle element is smaller than your target x, in which half of the array would you continue searching?
You may return -1 if the array does not contain the element x.
def binarySearch(array, x, low, high):
while low <= high:
mid = low + (high - low)//2
if array[mid] == x:
return mid
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
Solution & Explanation:
The recursive version would be as follows:
def binarySearch(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
if array[mid] == x:
return mid
elif array[mid] > x:
return binarySearch(array, x, low, mid-1)
else:
return binarySearch(array, x, mid + 1, high)
else:
return -1
We first need to check if the ending index (high) is greater than or equals to the starting index (low) for our search. If where we are supposed to end the search comes before where we start our search, we can conclude that the element x is not in the array.
If our starting index and ending index are fine, we go ahead with the search.
The base case remains the same as the iterative version. We return the index of the element once we find the element. This is the only base case we need because when high is equals to low, we are searching a range of size 1 (and so the middle element mid must be the only element in our range.)
If our middle element is bigger than our target element x, we can conclude that our target element is in the left side of mid (left half of array.) Remember, our array is sorted! So we do the recursive search from our current starting index up to one element before our current middle element. Otherwise, we search the array from the right side of mid (right half of array.)