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.

 1function BINARYSEARCHRECURSE(ARRAY, VALUE, START, END)
 2    # base case
 3    if START > END then
 4        return -1
 5    end if
 6    MIDDLE = INT((START + END) / 2)
 7    if ARRAY[MIDDLE] == VALUE then
 8        return MIDDLE
 9    else if ARRAY[MIDDLE] > VALUE then
10        return BINARYSEARCHRECURSE(ARRAY, VALUE, START, MIDDLE – 1)	
11    else if ARRAY[MIDDLE] < VALUE then
12        return BINARYSEARCHRECURSE(ARRAY, VALUE, MIDDLE + 1, END)
13    end if
14end function

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 10 and 12 to search the first half or second half of the array, whichever is appropriate.