0

I'm working on the PSet3 Find problem. Here's my code for the sort and search functions:

    bool search(int value, int values[], int n)
{
    if (value < 0)
        return false;
    else
    {
        int first = 0;
        int last = n - 1;
        if (first > last)
            return false;
        else
        {
            while (first <= last)
            {
                int middle = (first + last)/2;
                if (values[middle] < value)
                {
                    first = middle + 1;
                }
                else if (values[middle] == value)
                {
                    return true;
                    break;
                }
                else
                {
                    last = middle - 1;
                }
            }
        }
    }
    return false;
}

// Sorts array of n values
void sort(int values[], int n)
{
    for (int i = 1; i < n - 1; i++)
    {
        int temp = values[i];
        int j = i;
        while (j > 0 && temp < values[j-1])
        {
            values[j] = values[j-1];
            j--;
        }
        values[j] = temp;
    }
}

The problem is it fails one the checks:

check

I don't really understand what it means or how I could fix it.

It passes all other checks though:

Checking........
:) helpers.c exists.
:) helpers.c compiles.
:( sorts {5,4,3,2,1}
    expected "2", not "\n"
:) sorts {5,3,1,2,4,6}
:) finds 28 in {28,29,30}
:) finds 28 in {27,28,29}
:) finds 28 in {26,27,28}
:) finds 28 in {27,28,29,30}
:) finds 28 in {26,27,28,29}
:) finds 28 in {25,26,27,28}
:) doesn't find 28 in {25,26,27}
:) doesn't find 28 in {25,26,27,29}
:) doesn't find 28 in {29,30,31,32}
:) doesn't find 28 in {29, 30, 31}
:) finds 28 in {30,27,28,26}

Could you please help with it? Thank you in advance!

0

I think it should be

for (int i = 1; i < n; i++)

without the -1

3
  • You are right, it passes all checks now! Thank you!! But could you please explain why it should be just 'n' and not 'n-1'? Because in the pseudocode given in the CS50 explanation of insertion sort it's 'for i = 1 to n - 1'
    – jiayou
    May 3 '19 at 5:59
  • The pseudo-code means "1 to n-1, with n-1 included" (so <= n - 1, I prefer < n)
    – Blauelf
    May 3 '19 at 7:43
  • Oh I see, thank you for the explanation!
    – jiayou
    May 3 '19 at 13:29

You must log in to answer this question.

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