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

Question

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



}

Answer 1

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!

Answer 2

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.