Welcome to the Treehouse Community
Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.
Looking to learn something new?
Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.
Start your free trialDaniel Breen
14,943 PointsRecursive 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
231,184 PointsIf 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
Daniel Breen
14,943 PointsDaniel Breen
14,943 PointsSo the course content is wrong?
Steven Parker
231,184 PointsSteven Parker
231,184 PointsI think so! It looks like you've found a bug in the Java code:
You might want to submit a bug report to the Support folks. You might even get an "Exterminator" badge.
Daniel Breen
14,943 PointsDaniel Breen
14,943 PointsThanks Steven Parker!
Jeremiah Shore
31,168 PointsJeremiah Shore
31,168 PointsGood 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.
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
tostart >= end
, all tests pass exceptallInputValuesCanBeFound()
, which throws an AssertionError (the test case fails) and has the following output.Second, I changed the condition back to
start > end
and introduced the previously mentioned "off-by-one" error by changingmid - 1
tomid
in the first recursive call. When running the tests, all pass excepttargetBelowAllPresentValues()
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: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!