0

This is my find.c main function

int main(int argc, string argv[])
{
// ensure proper usage
if (argc != 2)
{
    printf("Usage: ./find needle\n");
    return -1;
}

// remember needle
int needle = atoi(argv[1]);

// fill haystack
int size;
int haystack[MAX];
for (size = 0; size < MAX; size++)
{
    // wait for hay until EOF
    printf("\nhaystack[%i] = ", size);
    int straw = GetInt();
    if (straw == INT_MAX)
    {
        break;
    }

    // add hay to stack
    haystack[size] = straw;
}
printf("\n");

// sort the haystack
sort(haystack, size);

int n;

for(n=0;n<size;n++)
    {
        printf("%i \n",haystack[n]);
    }

//try to find needle in haystack
if (search(needle, haystack, size)==1)
{
    printf("\nFound needle in haystack!\n\n");
    return 0;
}
else if(search(needle, haystack, size)==0)
{
    printf("\nDidn't find needle in haystack.\n\n");
    return 1;
}

}

And here is the header.c file...

#include <cs50.h>

#include "helpers.h"

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

bool binarysearch(int key, int array[], int min, int max);

bool search(int value, int values[], int n)
{
 return binarysearch(value, values, n-n, n-1);
}


bool binarysearch(int key, int array[], int min, int max)
{
//find midpoint value
int mid = (max+min)/2;

//check validity of midpoint
if(min>max || mid>max || mid<min)
{
    return false;
}

//check if midpoint = key
if(array[mid]==key || array[min]==key || array[max]==key)
{
    return true;
}


//check if midpoint is less/greater than key
if(array[mid] < key)
{
    binarysearch(key, array, mid+1, max);
}
else if (array[mid] > key)
{
    binarysearch(key, array, min, mid-1);
}

return false;
}





/*
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    int i,j,min,swap,marker;

    for(i=0;i<(n-1);i++)
    {
        min = i;

        for(j=i;j<n;j++)
        {
            if(values[j]<values[min])
            {
              min=j;
              marker = j;
            }
        }

        if(i!=min)
        {
            swap=values[i];
            values[i]=values[min];
            values[marker]=swap;
        }
    }

return;
}

When I compile and use check50, the following it outputted:

:) helpers.c exists
:) helpers.c compiles
:) finds 42 in {42,43,44}
:) finds 42 in {41,42,43}
:) finds 42 in {40,41,42}
:) finds 42 in {41,42,43,44}
:( finds 42 in {40,41,42,43}
   \ expected an exit code of 0, not 1
:) finds 42 in {39,40,41,42}
:) doesn't find 42 in {39,40,41}
:) doesn't find 42 in {39,40,41,43}
:) finds 42 in {42,40,39,41}

I am unsure why the program does not seem to function for this one particular test, it would appear that whenever the needle is in the third position of the array, the program fails to detect it.

Any help would be much appreciated.

Thank you in advance.

0

I believe the problem is with your implementation of a recursive function.

When a function returns a value and ends, the program goes back to the position it was in when that function was called. If the return value is not utilised, it will be lost forever. Therefore, when you create a recursive function, you have to pass the returned value back through the entire chain of recursions.

4
  • Thanks for your answer :) that seems to make sense. But I still don't understand why the program has worked in all other tests if that's the case? – VimDiesel Feb 21 '17 at 18:59
  • Looking at it now, perhaps when the midpoint is evaluated, any decimal is rounded down. This would mean that for the first three tests, the needle is found at either the max, min, or mid. And then for the 4th test it is found at the midpoint. For the 6th test it is the max again. However for the 5th it is neither, meaning the 5th case (the one where it isn't working) is the only one where the recursion actually comes into effect? – VimDiesel Feb 21 '17 at 19:01
  • Got it :) a return before calling the recursive function solved the issue. You're answer was spot on. Thanks again. – VimDiesel Feb 21 '17 at 19:07
  • Exactly what you said, glad you got it working! – Steve Bunting Feb 21 '17 at 19:39

You must log in to answer this question.

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