## 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.

# 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
{

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);
}
}
}
```

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

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.

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!