# What's wrong with this binary search implemented using recursion?

This is pset3 and I've tried making it work for numerous hours. It always returns false whether the 'needle' is found in the 'haystack' of arrays or not.

When typing this in the command window: ./generate 1000 50 | ./find 2008

It says "Didn't find needle in haystack." when actually, 2008 does exist in the haystack.

``````bool search(int value, int values[], int n)
{
//Binary Search with Recursion
int start;
int end;
int middle = n/2;

if(n==1)
{
if(value==values[middle])
{
return true;
}
else
{
return false;
}
}
else if(value<values[middle])
{
start = 0;
end = middle-1;
n = n/2;
int new_values[n];
//Add relevant values to the new array
for(int i=0; i<n; i++)
{
new_values[i]=values[start];
start++;
}
//Recurse
search(value, new_values, n);
return false;
}
else if(value>values[middle-1])
{
start = middle;
end = n;
n = n/2;
//Add relevant values to the new array
int new_values[n];
for(int i=0; i<n; i++)
{
new_values[i]=values[start];
start++;
}
//Recurse
search(value, new_values, n);
return false;
}
else
{
return false;
}

}
``````
• Your algorithm for binary search is not correct. You should try writing pseudo code first and also try execute code that you write. If you can't come up with any solution then watch walkthrough for pset3. If still you can't solve the problem just ask I will explain it to you. I didn't write answer directly because you wouldn't have understood exactly how recursion works and how to implement it correctly. Just ask if you need help.
– user2942
Nov 6, 2014 at 12:53
• I´m watching this question for a while too. I´m wondering whether you already wrote a non-recursive binary search that is working. If not I would advise that to you, since there are some logical flaws in your algorithm. And i would advise that you test your code with a hard coded array[20]. Nov 6, 2014 at 13:14

To spot what's wrong with your algorithm, given the following sorted array

``````{1, 2, 3}
``````

try with a pen and a paper finding these values

`value = 1` `value = 2` `value = 3` `value = 4`

And try to figure out why your algorithm returns false every time.

The algorithm is actually way simpler than that, but let's talk about recursion a little bit first.

A recursive function consists of 2 main sections

1. the base case section
2. the recursive section

The base case section is a case that if is met, then the current function call is the last call in the current chain (no more recursive calls are made in this chain).

The recursive section is obviously the one which contains our recursive call(s).

The pseudocode for binary search can be

``````bool binarySearch(int values[], int value, int start, int end)
{
// base case
if start > end
return false // we didn't find value

calculate the midpoint and store it in mid

if values[mid] is equal to value
return true // we found value
else if values[mid] < value
// throw away the right half of the array
"return" binarySearch(values, value, start, mid - 1)
// the remaining case: if values[mid] > value
else
// throw away the left half of the array
"return" binarySearch(values, value, mid + 1, end)
}
``````

As you can see,

1. we need a helper function because we need to pass extra information to the recursive call such as the newly calculated `start` or `end` and we can't do that with `search` because we're restricted with its declaration.
2. we don't set start to 0 manually every time
3. we don't check whether there's one element in the array
4. we don't need to create a new array to store the remaining half of the array
5. we return true if we found value, false if we didn't find it, or whatever the next call for `binarySearch` returns in case we're throwing one half of the array.

You might want to watch the short on binary search for more information!

• Ignore the previous comment, I made it work. Thanks for your help. Nov 7, 2014 at 7:21
• Hi Kareem, Thanks for your answer. I am a bit puzzled. In the instruction they specify not to alter the function declaration. Would not what you wrote be changing it? Thanks :) Jul 3, 2017 at 14:42
• @Guillaume_slize, this is actually a helper function which you may define and call from your original `search` function.
– kzidane
Jul 4, 2017 at 5:36

Your calculalation for middle is still wrong, TAKE PENCIL AND PAPER! and go through it for let´s say start = 0 and end = 20, and calculate BOTH cases(value < middle and value > middle), after 1st iteration you will see it.

But the syntax is pretty nice now.

• Thanks! I need to get used to using paper and pencil, I make too many stupid mistakes :/ ... Nov 7, 2014 at 9:18