Values found aren't the ones submitted?

Question

I'm working on pset3, and I think I've finished helpers.c. It sorts correctly, and I can't find any mistakes, but it does something really weird. If I enter the values 1, 2, 3, 4, 5 into find.c as hay, it sorts it, except it ends up as 0 ,1, 2, 3, 4. There's always a number missing and a 0 to replace it.

I use this code to sort:

void sort(int values[], int n)
{
   // TODO: implement an O(n^2) sorting algorithm
   int track = n;
   int check = 1;
   int hold;
   while (check != 0)
   {
      check = 0;
      for (int i = 0; i < track; i++)
      {
         if (values[i] > values[i + 1])
         {
            check++;
            hold = values[i];
            values[i] = values[i + 1];
            values[i + 1] = hold;
         }   
      }  
      track--;
   }

And I use this code to search:

bool search(int value, int values[], int n)
{
   // TODO: implement a searching algorithm
   int min = 0;
   int max = n;
   int x;
   while (max - min > 1)
   {
      x = round((max + min) / 2);
      if (values[x] < value)
         min = x;
      else if (values[x] > value)
         max = x;
      else
         return  true; 
   }
   return false;   
}

Can anyone please help me figure out what's wrong?

Answer 1

Initially, track is equal to n. Think about the situation when i is equal to track - 1 which is n - 1 and you try to access the value in values[i + 1]. Now, that's an invalid read because i + 1 in this case is equal to track and n and this index is beyond the array boundaries.

Also, usually, when we know the number of iterations beforehand (as we do in this case), we use for loops. On the other hand, while loops are used when we don't know the number of iterations (e.g., when we use a sentinel value to exit the loop).

For the search() function, your loop shouldn't be exiting even if max is equal to min (the difference is 0). So you're probably exiting a little bit early.

And since you're working with ints, no need to use round() as the digits after the decimal point are truncated anyway before even the call to round() is executed.

Lastly,

if values[x] < value 
    min should be x + 1 not x because values[x] was already tested
else if values[x] > value
    max should be x - 1 not x because, again, values[x] was already tested

Hope that helps! :)