Java Illuminated, 5th Edition

13.5 Binary Search: A Recursive Solution

We can use a binary search algorithm to search a sorted array for a given value.

Let’s look at how we can define a recursive solution to this problem. We will assume that the array is sorted in ascending order.

Again, we need to define the base cases and the general case, and the general case must reduce the size of the problem.

When searching for a value in an array, we have two possible outcomes:

• We find the value and return its array index.

• We do not find the value and return −1.

Overall, our strategy is this. First, we will look at the middle element of the array. If the value of the middle element is the value we are looking for, we will return its index. That is our first base case.

If the value ...