0

I wrote helpers.c according to Zamyla's walkthroughs. My code seems quite well to me. I checked it with check50 and it passes.

~/workspace/pset3/find/ $ check50 2016.find.less helpers.c
:) 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}
:) 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}
https://sandbox.cs50.net/checks/1e923dc608884ac0a28322482042a5b5

But, when I run it with

$ ./find 42
50
42
^d

it shows Didn't find needle in haystack. and so with ./generate 1000 50 | ./find 127 too. It simply doesn't work. Is there anything I missed?

My helpers.c code is

/**
 * helpers.c
 *
 * Helper functions for Problem Set 3.
 */

#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)
{
    // My binary search algorithm
    int start = 0;
    int end = n - 1;

    while (end >= start) 
    {   
        int mid = (start + end) / 2;

        if (values[mid] == value)
            return true;

        else if (value > values[mid])
            start = mid + 1;

        else if (value < values[mid])
            end = mid - 1;
    }

    return false;
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // My selection sort algorithm - O(n^2)
    int min_index, swap;

    for (int i = 0; i < n - 2; i++)
    {
        for (int j = i + 1; j < n - 1; j++)
        {
            if (values[j + 1] < values[j])
                min_index = j + 1;

            else if (values[j] < values[j + 1])
                min_index = j;
        }

        if (values[min_index] < values[i]) 
        {
            swap = values[min_index];
            values[min_index] = values[i];
            values[i] = swap;
        }
    }
}
0

The problem as it seems to me is in the implementation your sort() function. Yes, you have passed the cs50 but other than the last line of test :) finds 42 in {42,40,39,41} the other lines need not be sorted at all because either the array is already given sorted or the number does not exists in the array. The last line might be that that the array luckily passes the test due to finding 42 with binary search algorithm.

The cs50 check just assumes that it correct by checking for some predefined check set of values.

As you have mentioned that passing 50 42 gives incorrect result . This is because in the first for loop in the sort() function you have given condition i < n - 2. So in your case n is 2 (50 and 42) but the condition evaluates to false in the first case itself i.e 0 < (2 - 2) will evaluate to false so loop doesnt even run and the array is left unsorted and the binary search algorithm cannot find number 42.

So i recommend you to have a clear understanding of bubble sort algorithm from a good source and implement it correctly.

Hope that helped:)

Feel free to leave a comment if you have doubts.

2
  • You are right. Actually, my sorting function is not bubble sort, but selection sort. Anyway, I have reimplemented my algorithm by thinking through step by step. It doesn't work, at first. But, I realise I've never recompiled find.c before. Big mistake. I was only focusing on helpers.c. That's why my program is not affected by my implementation. It works quite well after compiling it. Thanks for your help. – Htet Oo Wai Yan May 4 '17 at 10:41
  • ..... u r wlcom:) – Vikrant Pradhan May 4 '17 at 13:41

You must log in to answer this question.

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