Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

Computer Science Introduction to Algorithms Algorithms in Code Binary Search Implementations

Recursive Binary Search Implementation: Infinite Loop

I implemented a Recursive Binary in C# (similar to the Java implementation). I end up with an infinite loop if I use just > rather than >= on the section below when the target value is not in the array.

Infinite Loop

if (start > end) 
{
    return -1
}

Works

if (start >= end) 
{
    return -1
}

I'm curious if I missed something? Here is my full implementation:

*Note: I'm aware of the improvements I can make to removing some of the redundancies where 'if' could be used instead of 'else if' and the unnecessary 'elses'. I just wanted the code to match the presented Java solution as closely as possible

namespace Algorithms.Search
{
    public class BinarySearch
    {
        public static int Search(int[] source, int target, int start, int end)
        {
            int mid = start + (end - start) / 2;

            // Only works with >=
            if (start >= end)
            {
                return -1;
            }
            else
            {
                if (target < source[mid])
                {
                    return Search(source, target, start, mid);
                }

                else if (target > source[mid])
                {
                    return Search(source, target, mid + 1, end);
                }
                else
                {
                    return mid;
                }

            }
        }
    }
}

Tests

using NUnit.Framework;

namespace Algorithms.Search.Tests
{
    [TestFixture]
    public class BinarySearchTests
    {
        private readonly int[] _intArray;

        public BinarySearchTests()
        {
            _intArray = new[] { 1, 2, 3, 4, 5, 6, 7, 8 };
        }

        [Test]
        [TestCase(2, 1)]
        [TestCase(6, 5)]
        [TestCase(0, -1)]       // Fails if just >
        [TestCase(9, -1)]       // Fails if just >
        [TestCase(999, -1)]  // Fails if just >
        public void Search_SortedIntegerArray(int target, int expected)
        {
            var index = BinarySearch.Search(_intArray, target, 0, _intArray.Length - 1);

            Assert.AreEqual(index, expected);
        }
    }
}

1 Answer

Steven Parker
Steven Parker
210,933 Points

If the target is smaller than any array value, then "start" will never be greater than "end". Eventually, both "start" and "end" will have the index of the first array item, and since "mid" will also be the same as "start", the function will call itself with the same arguments perpetually.

So it's important to test for equality as the limit condition

So the course content is wrong?

Steven Parker
Steven Parker
210,933 Points

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. :beetle:

Thanks Steven Parker!

Jeremiah Shore
Jeremiah Shore
31,168 Points

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!