Need help with pset3 find program

Question

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.

Answer 1

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.