Recursive Binary Search Implementation: Infinite Loop

So the course content is wrong?

I think so! It looks like you've found a bug in the Java code:

            if (target < input[mid]) {
                return binarySearch(input, target, start, mid);
//                                                        ^^^
// that should probably be:                               mid-1

You might want to submit a bug report to the Support folks. You might even get an "Exterminator" badge.

Thanks Steven Parker!

Good catch! I thought this whole situation was pretty interesting, and took a closer look. I think there are some finer points worth reviewing.

I found it odd that your last two test cases would fail, given the bug pointed out. This bug should only cause issues under certain conditions. Secondly, the >= portion of the logic has a different effect than the "off-by-one" error mentioned previously. Rather than try to describe it in text only, I'll provide some code to demonstrate what I mean.

I've been reading Pragmatic Unit Testing in Java 8 with J Unit, which I highly recommend for people who code in Java. The following examples were a great way to test some of the things I've been learning, and to more closely inspect this issue. I think, for the most part, the API of JUnit and the naming of the tests helps clarify the intentions of the test code. If anything isn't clear let me know, because that feedback would be really useful.

/* my binary search implementation, with the added improvement of an overloaded search method 
that sets the default search indicies automatically */

public class RecursiveBinarySearch {

    public static int search(int[] input, int target) {
        return search(input, target, 0, input.length - 1);
    }

    private static int search(int[] input, int target, int start, int end) {
        if(start > end)
            return -1;
        else {
            int mid = start + (end - start) / 2;

            if(target < input[mid]) {
                return search(input, target, start, mid - 1);
            } else if(target > input[mid]) {
                return search(input, target, mid + 1, end);
            } else {
                return mid;
            }
        }
    }

}

/* test code, using the JUnit testing framework */

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class RecursiveBinarySearchTest {
    private int[] input;

    @Before
    public void initializeInput() {
        input = new int[] {1, 2, 3, 4, 5, 6, 7, 8};
    }

    @Test
    public void successWhenTargetIsFound() {
        int result = RecursiveBinarySearch.search(input, 4);
        Assert.assertEquals(3, result);
    }

    @Test
    public void allInputValuesCanBeFound() {
        boolean result = true;
        for(int i = 0; i < input.length; i++) {
            int index = RecursiveBinarySearch.search(input, input[i]);
            System.out.printf("target: %d, index:%d%n", input[i], index);
            result &= index != -1;
        }
        Assert.assertTrue(result);
    }

    @Test
    public void negativeOneReturnedWhenTargetNotFound() {
        int result = RecursiveBinarySearch.search(input, 9);
        Assert.assertEquals(-1, result);
    }

    @Test
    public void targetBelowAllPresentValuesFails() {
        int result = RecursiveBinarySearch.search(input, -999);
        Assert.assertEquals(-1, result);
    }

    @Test
    public void targetAboveAllPresentValuesFails() {
        int result = RecursiveBinarySearch.search(input, 999);
        Assert.assertEquals(-1, result);
    }
}

In this unmodified state, the code works as expected, and all tests pass. The output isn't useful in this example, but I put that in there to help clarify the following issues.

First, I changed only the search condition of start > end to start >= end, all tests pass except allInputValuesCanBeFound(), which throws an AssertionError (the test case fails) and has the following output.

target: 1, index:-1
target: 2, index:1
target: 3, index:-1
target: 4, index:3
target: 5, index:-1
target: 6, index:5
target: 7, index:6
target: 8, index:-1

Second, I changed the condition back to start > end and introduced the previously mentioned "off-by-one" error by changing mid - 1 to mid in the first recursive call. When running the tests, all pass except targetBelowAllPresentValues() fails with a StackOverflowError; this is the "infinite loop" you mentioned. Understanding the stack data structure will help explain what this means, but basically, because the midpoint is checked but never eliminated from the base case, the program endlessly tries to check it until the stack runs out of memory.

Finally, I changed the code so both issues described were present at the same time. The result was that all tests were passing except for allInputValuesCanBeFound(), which again threw an AssertionError and had the following output:

target: 1, index:0
target: 2, index:1
target: 3, index:2
target: 4, index:3
target: 5, index:4
target: 6, index:5
target: 7, index:6
target: 8, index:-1

Again, this was mostly an exercise I did for myself to get a deeper understanding of what was going on here, as well as some practice with JUnit. I found it pretty neat how running tests like this help clarify very quickly what's going on with the code, without needing to debug or change the tests. Hopefully others will find this useful!