0

Updated with the solution on the bottom of this post. Thanks MARS for your help you got me headed in the right direction and I eventually got there.


I'm close to completing the helper challenge (less comfortable) but am having 2 problems that I am guessing are the same problem. I'll explain my problems, then post my code.

First, when I run check50 it returns that it finds or does not find each test correctly. However, it times out on several of the tests.

<code><pre>
:) helpers.c exists.
:) helpers.c compiles.
:( finds 28 in {28,29,30}
    timed out while waiting for program to exit
:) finds 28 in {27,28,29}
:( finds 28 in {26,27,28}
    timed out while waiting for program to exit
:( finds 28 in {27,28,29,30}
    timed out while waiting for program to exit
:) finds 28 in {26,27,28,29}
</code></pre>

Second, related issue. When I compile find myself and run the program, it just seems to stall. After populating the haystack it just returns an empty line. I can hit return for more empty lines or type whatever I want and it just doesn't do anything unless I Ctrl^C out of the program. There's screenshot below. The same happens when I hand enter the haystack or generate it with ./generate.

Screenshot

Finally, below is my code for helper.c. If the problem is in there I'd love to know. If I'm doing something else wrong, I'd love to know that too. Thanks ahead of time for your help.

    //Returns true if value is in array of n values, else false.
    bool search(int value, int values[], int n)
    {
        // TODO: implement a searching algorithm
        if (n <= 0)
        {
            return false;
        }

    while (n > 0)
    {
        int end = n;
        int start = 0;
        int middle = (start + end)/2;

        if (value == values[middle])
            {
            return true;
            }

        else if (value > values[middle])
            {
                start = middle + 1;
            }

        else if (value < values[middle])
            {
                end = middle - 1;
            }
    }
    return false;
}


//Sorts array of n values.
void sort(int values[], int n)
{
    // TODO: implement a sorting algorithm
    for(int i = 0; i < (n - 1); i++)
    {
        int min = i;
        int j, holder;

        //Find smallest element from i to n-1
        for (j = i + 1; j < n; j++)
        {
            if(values[j] < values[min])
            {
                min = j;
            }
        }

        //Exchange smallest element with the current i'th element
        //I couldn't figure out any other ways to do it than creating a holder for one value before changing that value.
        if (min != i)
        {
            holder = values[i];
            values[i] = values[min];
            values[min] = holder;
        }
    }
}


The solution I ended with. While I'm uncertain why it mattered, I ended up moving the declarations for int start, end, and middle around. For some reason when I placed the declarations for start and end above the while loop and the declaration for middle inside the while loop it worked. There were a couple of other changes you can see below, but no matter what I did I had the same problem with the infinite loop until I changed the locations of the declarations.

    int end = n-1;
    int start = 0;

    while (start <= end)
    {
        int middle = (start + end)/2;

        if (values[middle] == value)
            {
                return true;
            }

        else if (values[middle] < value)
            {
                start = middle + 1;
               // printf("Values[middle] < value. New start = %i\n", start); //Trying to find bug causing infinite loop
            }

        else if (values[middle] > value)
            {
                end = middle - 1;
                //printf("Values[middle] > value. New end = %i\n", end); //Trying to find bug causing infinite loop
            }
    }
    return false;
}
1

It seems that your search program has an infinite loop, it is almost always the fault of the end condition while loop, make sure that the loop breaks at some point, I suspect the program will work if we change the condition to something a little more readable:

while (start <= end)
5
  • Unfortunately, that didn't work, even if it makes my code better. This is what I've found. I get the same infinite loop result no matter the order of the conditions in the while statement. I can add a "break;" after the final "if else", which does break it out of the loop. But it doesn't give me the right result every time. I've done a lot of research about iterative binary searching. I think my code for searching is actually okay. Unless someone sees something else wrong with my search code, it must be in my sorting code, right? Any thoughts? – Clayton Ingalls Sep 6 '17 at 17:51
  • Nevermind. There's definitely a problem with my search code. I haven't found it yet. But I added some printf's in each condition to tell me the new start or new end. And it just prints forever. Back to the drawing board. – Clayton Ingalls Sep 6 '17 at 18:22
  • I've added a little code for debugging. else if (values[middle] > value) { end = middle - 1; printf("Values[middle] > value. New end = %i\n", end); //Trying to find bug causing infinite loop } It returns the following forever.<br/> Values[middle] > value. New end = 0 Values[middle] > value. New end = 0 Values[middle] > value. New end = 0 – Clayton Ingalls Sep 6 '17 at 18:44
  • Can you publish your complete code? just out of curiosity I would like to use gdb to debug the code and see exactly where your infinite loop occurs – MARS Sep 6 '17 at 19:28
  • I guess it's my fault for not seeing it, these variables are initialized to 0 and n-1 in each iteration of the loop, so it never ends, congratulations to you (and a zero for me)., you can accept your own question so that it does not appear in the forum as unanswered – MARS Sep 6 '17 at 19:48
1

Victory! I figured out the problem and I don't really know why it fixed it. I moved the declaration of int end and int start to just above the while clause. I left the declaration of int middle inside the while clause. And like that the infinite loop stopped and all the tests came back correct. How can such a little thing make such a big difference?

1
  • Thank you! I had the exact same problem, very frustrating. I also don't exactly understand why this makes such a big difference... – Larsen Jörn Marquardt Dec 21 '17 at 15:38

You must log in to answer this question.

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