0

First, thanks for helping me on this!

My search function work with the tests: ./generate 1000 50 | ./find 127 -> "Found needle in haystack!" ./generate 1000 50 | ./find 128 -> "Didn't find needle in haystack."

However, it fails the check50 2014.fall.pset3.find helpers.c:

:) helpers.c exists

:) helpers.c compiles

:) finds 42 in {42,43,44}

:( finds 42 in {41,42,43} \ expected an exit code of 0, not 1

:( finds 42 in {40,41,42} \ expected an exit code of 0, not 1

:( finds 42 in {41,42,43,44} \ expected an exit code of 0, not 1

:( finds 42 in {40,41,42,43} \ expected an exit code of 0, not 1

:( finds 42 in {39,40,41,42} \ expected an exit code of 0, not 1

:) doesn't find 42 in {39,40,41}

:) doesn't find 42 in {39,40,41,43}

This is my search function - any ideas?

bool search(int value, int values[], int n)
{
// false if n is negative
if (n < 0)
{
return false;
}    

// binary search
int min = 0;
int max = n-1;
int mid;

// check as long as there is a list
while (min <= max)
{      
    mid = (min + max) / 2;

    if (values[mid] == value)
    {
        return true;
    }     
    else if (value < values[mid])
    {
        max = mid - 1;
    }    
    else
    {
        min = mid + 1;
    }
}
return false;
}


void sort(int values[], int n)
{
// bubble sort
int swap = true;

// go through the values at least once 
do
{ 
    swap = false;
    int new_i;

    for (int i = 0; i <= n; i++)
    {
        // switch values, if left is bigger than right    
        if(values[i] > values[i+1])
        {
            new_i = values[i+1];
            values[i+1] = values[i];
            values[i] = new_i;
            swap = true;
        }
    }
}
// if there was a swap, go again
while (swap == true);
return;
}
1

Since the search code seems to be working correctly, I would say that the problem lies elsewhere. The most common problem in this situation is that the sort isn't working correctly. Remember, a binary search depends on the list being sorted correctly. You might try printing out the sorted list and verifying that it is in fact sorted for the test scenarios.

It could also be something as simple as a typo in the code, returning 1 when you actually wanted to return 0. Also, if you are returning true/false from main to the operating system, remember that false translates to 0, even though returning 0 is the conventional return for successful completion of a program.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

| improve this answer | |
  • Thanks for your reply. Everything seems to be sorted correctly. I used this in find.c: // sort the haystack sort(haystack, size); // print sorted list for (int i = 0; i < size; i++) { printf("%i \n", haystack[i]); } All numbers that are printed are also sorted. I don't need to sort the list within the search function, do I? – Frederic Knaudt Dec 6 '15 at 20:13
  • No, the list needs to be sorted only once. BTW, you didn't change anything in find.c, did you? – Cliff B Dec 6 '15 at 20:21
  • Also, have you tested with the input that check50 uses instead of ./generate? – Cliff B Dec 6 '15 at 20:28
  • I didn't change anything in find.c nor code of generate.c. Can I input the arrays in the command line somehow to test as you suggested? I also pasted the sort function above in my post to look at. – Frederic Knaudt Dec 6 '15 at 21:08
  • No, not as command parameters. You execute the code with a single parameter, the number to find, ./find 42 will search for 42. Next, it will ask you to input the numbers in the array. Keep entering numbers, one at a time until you have entered your list of numbers. Once all the numbers are entered, hit CTRL-D to terminate the data input. The program will then execute. – Cliff B Dec 6 '15 at 21:15

You must log in to answer this question.

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