Binary Search, Recursively

In the previous section we implemented binary search iteratively, using a loop to keep track of the range we are still searching. In this and several upcoming sections, I will show you how to write it recursively.

I am going to assume you have seen recursion before. Recursion is typically a confusing topic for beginner students, though, so I will walk you through writing a recursive method, using binary search as the example. We will revisit recursion later in the course.

To start, let’s work with this definition of recursion: a recursive method solves a problem by calling itself on a smaller version of the same problem. Binary search already has that shape.

• The problem is to search for a target value in a sorted array.
• We look at the middle element and compare it to the target.
• If they are equal, we are done.
• If not, what is left to do is to search for the target in either the left half or the right half. That is the same problem again, just on a smaller array. So we can call binary search on that half.
• We keep doing this until we find the target or the half we are searching is empty.

Look at the fourth bullet. That is the recursive step. In the iterative version, the loop is what sends us back to look at the middle of the new range. A recursive call sends us back the same way. The difference is that in the recursive version we do not have to describe the new range with variables we update. We just call the method on that half.

Here is our method signature from before:

public static int binarySearch(int[] arr, int target) { ... }

I will make one small change first. Let’s return true if the target is found and false otherwise, instead of returning the index. If we return the index, we have to translate an index in a half back into an index in the original array. That bookkeeping adds complexity to the code and distracts from the recursive structure. If we do not return the index, we can keep our attention on the recursive structure. Here is the modified signature:

public static boolean binarySearch(int[] arr, int target) { ... }