Recursive Binary Search
The recursive implementation of binary search is very similar to the iterative approach. However, this time we also include both
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.