pset3 code not finding any numbers when in helpers.c

Question

// TODO: implement a searching algorithm
if(n <= 0)
{
    return false;
}

int end = n;
int start = 0;
int middle = (start + end)/2;
int found = 0;

while(found == 0)
{
    if(value == values[middle])
    {
        found = 1;
        return true;
    }
    else if(value > values[middle])
    {
        start = middle;
    }
    else if(value < values[middle])
    {
        end = middle;
    }
    if(values[start] == value)
    {
        found = 1;
        return true;
    }
    middle = (start + end)/2;
    if(end - start == 1)
    {
        found = 2;
        return false;
    }
}
return false;



// TODO: implement a sorting algorithm

 int checkArray[65356] = {0};

 for(int i = 0; i < 11 ; i++)
 {

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

 }
 int counter = 0;
 int repeats;
 for(int i = 0; i < n; i++)
 {
      if(checkArray[i] > 0)
      {
          repeats = checkArray[i];
          while(repeats > 0)
          {
                values[counter] = i;
                repeats -= 1;
                counter += 1;
          }

      }
 }
 for(int i = 0; i < 11; i++)
 {
      printf("%i\n", values[i]);
 }

return;

My code for find(more) in pset3 is not finding any numbers from generate. I have copied the same code into a different file to make it search from a pre defined array and that works perfectly. However, when I run find, the code doesn't find anything.

Any help would be appreciated.

Answer 1

The code

 for(int i = 0; i < 11 ; i++)
 {

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

 }

makes little sense to me, especially the use of i and j. So j runs in the range of the array index. But then it is used as an index to checkArray, which should receive values as input, like checkArray[values[j]] += 1;. i on the other hand runs over values from 0 to 10 (pretty arbitrary numbers) and is used as an index to values, which should take values from 0 to n (excluded) instead. So both your variables seem to serve the same purpose while being used in a wrong way, you should be able to use only one loop with one variable.

Your search seems a bit more complex than required.

If you changed your loop to run only while start < end (depending on end being excluded from the search interval as it often is by convention), you could remove that if(end - start == 1).

Slightly changing another line to start = middle + 1; fixes an infinite loop when searching for an element that's larger than the only element in the search interval. Like for example an array [1] and searching for 2. Without the +1, start would stay at 0 and not move at all.

The if(values[start] == value) block makes no sense to me. If that one is true, it should trigger the if(values[middle] == value) eventually, maybe after a few more iterations.

If you calculated middle at the beginning of the loop, you would not need the same formula twice in your code.