Recursive Binary Search
The recursive implementation of binary search is very similar to the iterative approach. However, this time we also include both start
and end
as parameters, which we update at each recursive call. The pseudocode for a recursive binary search is shown below.
function BINARYSEARCHRECURSE(ARRAY, VALUE, START, END) (1)
# base case
if START > END then (2)
return -1 (3)
end if (4)
MIDDLE = INT((START + END) / 2) (5)
if ARRAY[MIDDLE] == VALUE then (6)
return MIDDLE (7)
else if ARRAY[MIDDLE] > VALUE then (8)
return BINARYSEARCHRECURSE(ARRAY, VALUE, START, MIDDLE – 1) (9)
else if ARRAY[MIDDLE] < VALUE then (10)
return BINARYSEARCHRECURSE(ARRAY, VALUE, MIDDLE + 1, END) (11)
end if (12)
end function (13)
The recursive version moves the loop’s termination condition to the base case, ensuring that it returns -1 if the start
index is greater than the end
index. Otherwise, it performs the same process of calculating the middle
index and checking to see if it contains the desired value
. If not, it uses the recursive calls on lines 9 and 11 to search the first half or second half of the array, whichever is appropriate.