0

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 '14 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]. – SebBr Nov 6 '14 at 13:14
6

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. – rohan Nov 7 '14 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 :) – Guillaume_slize Jul 3 '17 at 14:42
  • @Guillaume_slize, this is actually a helper function which you may define and call from your original search function. – Kareem Jul 4 '17 at 5:36
-1

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 :/ ... – rohan Nov 7 '14 at 9:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .