Pset3 - Code sorts, but does not find the needle using generate

Question

I have the following code for helpers.c. When I run find, if I input numbers by hand, it sorts them and finds/doesn't find the n correctly. However, when I use generate to input the numbers, I can see that they are sorted, but it always returns that there is no needle in the haystack. I have not changed generate.c, other than to add comments. Any advice would be greatly appreciated! Thanks!

#include <cs50.h>
#include <stdio.h>
#include "helpers.h"


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

bool search(int value, int values[], int n)
{

// Set values for the top and bottom of the search
int lower = values[0];
int upper = values[n-1];  

// Do not allow negative numbers
if (n < 0)
{
    return false;
}

// Binary search
while (lower <= upper) 
{

//Set middle
    int middle = (upper + lower) / 2;

    //Compare value to middle, cut search in half

    if (values[middle] == value)
    {
        return true;
    }
    if (values[middle] < value)
    {
        lower = middle + 1;
    }
    if (values[middle] > value)
    {
        upper = middle - 1;
    }  
}
return false;
}

/**
* Sorts array of n values.
*/
void sort(int values[], int n)
{
// TODO: implement an O(n^2) sorting algorithm
// Cycle through array
for (int k = 0; k < n - 1; k++)
{
    //Optimize; check if there are no swaps
    int swaps = 0;

    //Swap adjacent elements if out of order      
    //Iterate through the array
    for (int i = 0; i < n - 1 - k; i++)
    {
        // Check if array[i] and array[i+1] are in order
        if (values[i] > values[i+1])
        {
            int temp = values[i+1];
            values[i+1] = values[i];
            values[i] = temp;
            swaps++;
        }
        else if (swaps == 0)
        {

        }
        }
}


//To print the sorted array
for (int a = 0; a < n; a++)
{
    printf("%i, ", values[a]);
}
printf("\n");

}

Answer 1

Your sort is flawed, causing it to eject the largest value and add 0 to the list. Look at the printout of the list to confirm.

In the first pass through the outer for loop, k=0. This allows i to become n-1. But that interacts with your swap sequence. You swap values[n-1], the last element in the array, with values[n], an undefined element. This introduces the 0 and ejects the largest element in the list. (I've never understood why this doesn't produce an error, but it doesn't.) The sort program goes outside the range of elements in the values[] array and resuts in the loss of an element.

IN addition, lifelonglerner has found a flaw in the search routine.

If this answers your question, please accept the answer to remove your question from the unanswered question pool. Let's keep up on forum maintenance. ;-)

Answer 2

You have defined lower, upper, and middle to start with as the first value, the last value, and the average of the first and last values. Watch the videos for binary search (I thought Zamyla's walkthrough to be the clearest outside of the lecture). What you are taking isn't the average of any of the values in the array, but rather the middle point within the array. If you have an array of size 7, then the middle value would be the 3rd position of that array. You look at what value then resides at the 3rd position and determine whether you got lucky (just happens to match your needle), whether your needle lies to the left of the value in position 3 (needle < array[3]), or whether your needle lies to the right of the value in position 3 (needle > array[3]).

So on your first pass through, your lower should be 0 (the first position within the array) and your upper should be n (the last position of the array). The first middle will be an average of these two because you are looking for the middle position of the array, not the average of the array's values.

Hope that makes sense.