0

I am working on helpers.c in pset3. I have the following code. Find.c compiles with helpers.c, but when I run it with "./generate 1000 50 | ./find 127", it lists lines with "haystack[n] =" where n = every number between 1 and 1000. And then it says it didn't find a needle in the haystack. I am not sure what the listing of the "haystack[n]" is, or how to fix my code from here.

Here is the helpers.c code I am using:

#include <cs50.h>

#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 */

bool search(int value, int values[], int n)
{
// Set values for the top and bottom of the search
    int lower = values[0];
    int upper = values[n-1];

//Find middle
    int middle = (upper + lower) / 2;

// Binary search
    while (lower <= upper)
    {
    //Compare value to middle, cut search in half
        if (values[middle] == n)
        {
            return true;
        }
        else if (values[middle] < n)
        {
            lower = middle + 1;
        }
        else if (values[middle] > n)
        {
            upper = middle - 1;
        }      
    }
    return false;
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    // Cycle through array
    for (int k = 0; k < n - 1; k++)
    {
        //Optimize; check if there are no swaps
        int swaps = 0;

        //Swap adjacent elements if out of order      
        //Iterate through the array
    for (int i = 0; i < n - 1 - k; i++)
    {
        // Check if array[i] and array[i+1] are in order
        if (values[i] > values[i+1])
        {
            int temp = values[i+1];
            values[i+1] = values[i];
            values[i] = temp;
            swaps++;
        }
        else if (!swaps)
        {
        break;
        }

    }
    return;
}
return;
}
1

It looks like you've confused two parameters in your search function.

bool search(int value, int values[], int n)

My understanding of the function is that value is the target that you are looking for in the values[] array, and n is the number of elements in the array. However, you are searching the array for n and not for value.

Also, you initialize middle before entering the while loop, but middle also needs to change with each pass through the while loop based on the updated values of upper and lower.

As for all of the haystack[x]= printouts, that's normal. THe program prints that to the screen, as it is supposed to, but gets it's input for each one from ./generate instead of from user input.

If this answers your question, please accept this answer to remove the question from the unanswered question pool. Let's keep up on forum housekeeping. ;-)

  • Ah! Thanks so much! Something so simple to overlook. I have changed "n" to "value". I changed a few more things, and I thought I was getting somewhere. Now if I generate 10 numbers, any value I try to find always returns true. But if I generate 1000 numbers, any value I find is always false. I am not sure what would cause this. Any advice on what to look for? – REW Jul 16 '15 at 18:55
  • Without knowing what you've changed, I have no way to answer that. But if you had made only the changes noted, it should work. – Cliff B Jul 16 '15 at 19:55
  • REW, Have you verified that your sort is working properly? Since binary requires a presorted array, an error in the sort routine might produce bizarre results? – lyflonglerner Jul 16 '15 at 23:12
  • I have used printf, and I can see that numbers are sorting. If I just enter several numbers by hand, it sorts them, and it works correctly. However, if I use generate to input the numbers, it sorts the number, but it never finds the number, even if it is there. Would it help if I posted my code again? – REW Jul 17 '15 at 1:34
  • @REW. I am also getting similar errors. If I use linear search,everything is fine. If I use binary search very similar to your code, check50 passes all the tests ,find works manually to find the needle. But if you pipe the results using ./generate 1000 50 |./find 127,it does not work. I will be interested to know whether you have traced thecause of this error. uma1966 – uma1966 Aug 25 '15 at 23:23

You must log in to answer this question.

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