pset3: Implementation of FIND is killed by server.

Question

I am stuck at the implementation of FIND of cs50 pset3. I have completed my implementation of SEARCH and SORT in helpers.c, but when I run check50 I am being notified that the process has been killed by the server on two occasions ("killed by server"). I can only assume that my program gets stuck in an infinite loop on specific occasions and the server is forced to kill it. However, I am really puzzled since it seems as if the program is doing everything right even if the server kills it (finds 42 when there is a 42 and doesn't find 42 when there isn't a 42). I have run update50.

I appreciate any help. Please see my code and the error message below.

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

bool search(int value, int values[], int n)
{
int start = 0; 
int end = n-1; 

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

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

    else if (values[mid] > value)
    {
        start = mid - 1; 
    }

    else 
    {
        start = mid + 1; 
    }
}
return false; 
}

// Sorts array of n values.
void sort(int values[], int n)
{
for (int i = 0; i < n; i++)
{
    int min = i;
    for (int j = i + 1; j < n; j++)
    {
        if (values[j] < values[min])
        {
            min = j;
        }

        int temp = values[min];
        values[min] = values[i];
        values[i] = temp;
    }
}
}

:) helpers.c exists

:) helpers.c compiles

:( finds 42 in {42,43,44} \ killed by server

:) 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} \ killed by server

:) finds 42 in {42,40,39,41}

Answer 1

Herein lies the problem:

else if (values[mid] > value)
{
    start = mid - 1; 
}

Consider this pseudocode:

// return true if value equals values[mid] 
// if value < values[mid], update max index
// if value > values[mid], update min index

When you adjust your minimum and maximum indices ("start" and "end" in your case), you need to consider whether the value you are looking for is to the right of (less than) or to the left of (greater than) that midpoint value. The former will require you to change the upper bound of the indices within which you are searching; the latter will require you to change the lower bound.