Recursion

One search method that relies on the use of recursion is binary search.

A binary search finds the middle of an array and tests that point. If the target is greater than the midpoint value, then the search eliminates the lower half. Likewise, if the target is less than the midpoint value, the top half can be eliminated. This process is then repeated, finding a new midpoint each time. It’s important to note that the array must be sorted for a binary search to work properly.

Here is this search in action:

Notice how each iteration eliminates half of the values. While this process is slightly more efficient for smaller arrays, it is significantly more efficient for larger arrays. A linear search of 10,000 records could have a worst case scenario of 10,000 comparisons. With binary search, the worst case is only 15 comparisons to find the value.

When comparing Linear Search to Binary Search, there are a few significant differences. First, binary searches are much more efficient than linear searches. Second, linear searches will work on any array, but binary searches only work on a sorted array. Finally, the algorithm for binary searches is a little more complex than our linear search.

Here is a non-recursive implementation of binary search:

public int binaryLoop(int[] array, int target) {
    int begin = 0;
    int end = array.length - 1;

    while (begin <= end) {
        int mid = (begin + end) / 2;
        if (target < array[mid]) {
            end = mid - 1;
        }
        else if (target > array[mid]) {
            begin = mid + 1;
        }
        else if (target == array[mid]) { 
            return mid;
        }
    }
    return -1; // not found
}

Notice in the loop how the midpoint is calculated, then tested before updating the beginning and ending points each time based on the results. Initially, the array is passed to the method, where the values begin and end are set to the first index and the last index in the array. The while loop then checks that begin is less than end, and calculates the midpoint of the array. The method then checks if the target value is greater than, less than, or equal to the midpoint. If the target is greater than the midpoint, then the method removes the begin to midpoint values from the search. As noted earlier, this only works if the values are sorted before being searched. The method then returns to the beginning of the while loop, and finds a new midpoint between the new begin value and the end. It does so until the target has been found, or the array has been fully halved and searched.

This method can also be written using recursion. Since recursion attempts to create a simpler version of a problem each time a recursive method is called, binary search lends itself well to its use, as the array is reduced in size each time, all the way to a single value at times. Here is the implementation of binary search with recursion:

public int binaryRec(int[] array, int target, int begin, int end) {
    int mid = (begin + end) / 2;

    if (target == array[mid]) { 
        return mid; // Base Case
    }

    if (target < array[mid]) {
        return binaryRec(array, target, begin, mid - 1);
    }

    if (target > array[mid]) {
        return binaryRec(array, target, mid + 1, end);
    }
    return -1;  //Alternate Base Case
}

The biggest change at the start of this code is that the beginning and ending values are being passed into the method. From there, the midpoint is calculated the same way as before.

The base case is where the value is found. In the first iteration, the base case is skipped, and the recursive case is called. The recursive call passes the original array, the target value, but then updates the starting point as it makes the call. Once the value is found, the index value of the target is then returned back through each of the recursive return statements until it eventually gets back to the original call statement.

How many times does a binary search need to execute to find its value? Recall from our lesson that the number of iterations is roughly a log base 2 relationship.

In this exercise, you are going to calculate the maximum iterations and the actual iterations needed to find a random value in arrays of size 500, 5000, 50k, and 500k.

You are given helper methods to calculate the maximum iterations, generate the random array, and do the binary search. You are also given a counter variable that increments each time your recursive binary method is called.

You will need to come up with the remainder of the code.

Sample Output

Array Size: 100
Max iterations: 7
Actual iterations: 5

Array Size: 1000
Max iterations: 10
Actual iterations: 5