0

The following code will enter an endless loop when my needle is 1 and my haystack consists of the array [1,2,3].

/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n)
{
    if (n>=0)
    {
        while (n>2)
        {
            int middle = n/2;
            if (values[middle]==value) return true; // Line 26 - this works
            else if (values[middle]>value)
            {
                int newvalues[middle];
                for (int i=0; i<middle; i++) newvalues[i]=values[i];
                search(value, newvalues, middle);
            } // Line 32 - where I end up after Line 43
            else if (values[middle]<value)
            {
                int newvalues[middle];
                for (int i=0; i<middle; i++) newvalues[i]=values[i];
                search(value, newvalues, middle);                
            }
        }
        if((values[0]==value) || (values[1]==value)) 
        {
            printf("values[0] is %i and values[1] is %i\n", values[0], values[1]);
            return true; // Line 43 - does not work
        }
    }
    return false;
}

I step through the code in gdb and everything works fine until I get to the return true;on Line 43. When I take the next step I end up on line 32 and I seem to have the original array (n should be 1 but it is 3 and it contains the original data.

This results in an endless loop even though search executes the return true; statement.

With other needles and haystacks, the program works but I think that is because it reaches the return statement on line 26 (e.g. needle=1, haystack = [1,2]; needle = 2, haystack = [1, 2, 3])

2

regardless of the correctness of the algorithm, generally speaking, if you want a function to return the value of an expression, you may return the expression itself. for example:

return 16 + 26; // returns 42

similarly, if you want a function to return the value returned by a call to another function, you return that call. for example, to return the value returned by a call to foo from bar, you may do the following:

int foo(void) {
    return 42;
}

int bar(void) {
    return foo(); // returns the value returned by the call to foo (here 42)
}

recursive functions are the same. it's just that a recursive function calls itself. if you want to return the value returned by the recursive call, you return the recursive call itself.

4
  • Thanks Kareem. I did find the answer after I posted but this explains the reason a little bit more clearly. I have another question that I'm not sure needs another posting. By initializing so many arrays, am I making a mess of my stack? Should I be using malloc & free? The procedure works with an array of size 1000 but I am not sure if this is really reliable. Jan 25 '16 at 13:19
  • @BrendanRafferty I will answer that, but probably you should post it as a separate question for the sake of organization and for future references!
    – kzidane
    Jan 25 '16 at 13:20
  • I will post a question but it will take a while. I will have to clean this up a bit and compare to other code I have seen on StackExchange. Thanks again. Jan 25 '16 at 13:22
  • @BrendanRafferty no problem. take your time! just link me to it when you're done!
    – kzidane
    Jan 25 '16 at 13:23

You must log in to answer this question.

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