0

I've been working of the find (problem set 3) for 2 weeks and I'm just stuck.

I already have the design etc worked out but there is a bug that I seem to be missing.

So the problem is that when I run it through the check (check50 2015.fall.pset3.find helpers.c) I keep getting this:

error when checking

I also checked the printout of my own error messages which showed me that something was wrong, although I don't exactly understand why, it seems that the program only finds the needle if it is the first of the array... which doesn't make any sense to me at all.

For example - this works (sorting clearly works) ./find 42 haystack[0] = 43 haystack1 = 44 haystack[2] = 42 haystack[3] = (cancelled here) - 43 44 42 - 43 42 44 - 43 42 0 - 42 43 0 - 42 0 43 - 42 0 43 - 0 42 43 - 0 42 43 - 0 42 43 - 0 42 43 - 0 42 43 - 0 42 43 - 0 42 43 - 42 Found needle in haystack!

But this doesn't: ./find 42 haystack[0] = 40 haystack1 = 43 haystack[2] = 42 haystack[3] = (canceled here) - 40 43 42 - 40 42 43 - 40 42 0 - 40 42 0 - 40 0 42 - 40 0 42 - 0 40 42 - 0 40 42 - 0 40 42 - 0 40 42 - 0 40 42 - 0 40 42 - 0 40 42 - 40 - 40 upper half - Bug40 mid value - first 2 last 2 mid 1 Didn't find needle in haystack.

Here is my helpers.c file for reference - I have printf statements throughout as I find it more convenient that the GBD. /** * helpers.c * * Computer Science 50 * Problem Set 3 * * Helper functions for Problem Set 3. */

#include <cs50.h>
#include <stdio.h>
#include "helpers.h"

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

//function declaration
void swap(int *a, int *b);
void sort(int values[], int n);

bool search(int value, int values[], int n)
{
    //intialize variables to calculate mid
    int first = 0;
    int last = n - 1; //array is zero indexed TODO Check if this is correct
    int evencheck = (first + last);
    //to ensure mid rounds up to the nearest whole number
    if (evencheck%2 > 0)
    {
        evencheck++;
    }

    int mid = (evencheck/2);

    while (first < last)
    {
        int check = mid;
        if (value == values[mid])
        {
            //my check
            for (int s = 0; s < n; s++)
            {
                printf("%d ", values[s]);
            }
            printf("\n");

            printf("%d\n", values[mid] );

            return true;
            break;
        }
        else if (value < values[mid])
        {
            //search in lower half
            //my check
            for (int s = 0; s < n; s++)
            {
                printf("%d ", values[s]);
            }
            printf("\n");

            printf("%d lower half \n", values[mid] );

            last = mid - 1;

            printf("%d lower half \n", values[mid] );

        }
        else if (value > values[mid])
        {
            //search in upper half
            //my check
            for (int s = 0; s < n; s++)
            {
                printf("%d ", values[s]);
            }
            printf("\n");

            printf("%d\n", values[mid] );

            first = mid + 1;

            printf("%d upper half \n", values[mid] );
        }

        int count = 0;
        //if needle not found
        if (check == mid)
        {
            count++;
        }
        if (count > 1)
        {
            return false;
            break;
        }
    }
    //to fix end of non-void function
    printf("Bug");
    printf("%d mid value \n", values[mid] );
    printf("first %d last %d mid %d \n", first, last, mid );
    return false;

}


//sorting fxn
void sort(int values[], int n)
{
    // Bubble sort
    bool sorted = false;
    //find the smallest number
    do
    {
        //swap according to value of number (smallest to greatest) as long as unsorted
        sorted = true;
        for (int i = 0; i < n; i++)
        {
            if (values[i] > values[i+1])
            {
                swap(&values[i], &values[i+1]);
                sorted = false;
            }
            //my check
            for (int s = 0; s < n; s++)
            {
                printf("%d ", values[s]);
            }
            printf("\n");
        }
    }
    //as long as there is one swap, sorted will be false & program will iteratee.
    while (sorted == false);
    return; // when the final pass is done
}

//swapping fxn
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
1

Your problem lies in these lines:

    for (int i = 0; i < n; i++)
    {
        if (values[i] > values[i+1])

If there are n elements in array values[], what happens when i=n-1 and you try to look at values[i+1]? What is i+1? Is it a legal value for an array element?

This causes an element to be sorted out the end of the array and a 0 to be introduced and sorted into the array.

There are other problems waiting, but they aren't part of your question. Can't take all the fun away! ;-)

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

You must log in to answer this question.

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