0

I am working on pset 3 for cs50 on edx, and I'm having quite a bit of trouble with the binary search problem. My program worked fine when I tested it with a linear search (so I think the problem isn't in my sort), but I can't figure out what I'm doing wrong. check50 shows that it finds the "needle" sometimes but other times it doesn't, and I haven't had luck with it testing it on my own. Any help would be greatly appreciated :)

Here's my code (with linear search commented out)

/**
 * helpers.c
 *
 * Helper functions for Problem Set 3.
 */

#include <cs50.h>

#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n)
{
    // TODO: implement a searching algorithm

    /*
    //LINEAR SEARCH:
    for (int i = 0; i < n; i++)
    {
        if (values[i] == value)
        {
            return true;
        }
}
return false;
*/


// BINARY SEARCH
int mid;
int min = 0;
int max = (n - 1);
while (n > 1)
{
    // calculate the middle index
    mid = (min + (max - min) / 2);

    // check if middle index is the "needle"
    if (values[mid] == value)
    {
        return true;
    }

    // if the "needle" is lower than the middle index, adjust max
    else if (values[mid] > value)
    {
        max = (mid - 1);
    }

    // if the "needle" is higher than the middle index, adjust min
    else if (values[mid] < value)
    {
        min = (mid + 1);
    }

    // count the elements in question
    n = ((max - min) + 1);
}

// if "needle" can't be found return false
return false;

}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // TODO: implement a sorting algorithm
    // BUBBLE SORT
    int swaps;
    do
    {
        swaps = 0;
        for (int j = 0; j < n; j++)
        {
            if (values[j + 1] > values[j])
            {
                int store = values[j];
                values[j] = values [j + 1];
                values[j + 1] = store;
                swaps++;
            }
        }
    }
    while (swaps > 0);
    return;
}

Also, here's what check50 returns:

~/workspace/pset3/find/ $ check50 2016.find.less helpers.c
:) helpers.c exists
:) helpers.c compiles
:( finds 42 in {42,43,44}
   \ expected an exit code of 0, not 1
:) finds 42 in {41,42,43}
:( finds 42 in {40,41,42}
   \ expected an exit code of 0, not 1
:( finds 42 in {41,42,43,44}
   \ expected an exit code of 0, not 1
:) finds 42 in {40,41,42,43}
:( finds 42 in {39,40,41,42}
   \ expected an exit code of 0, not 1
:) doesn't find 42 in {39,40,41}
:) doesn't find 42 in {39,40,41,43}
:( finds 42 in {42,40,39,41}
   \ expected an exit code of 0, not 1

Thanks again for any help, sorry for long post

1

No looks like the problem is in sort. Linear sort is working indeed because it doesn't depend on correct sort, but binary does.

And the problem is that you sort in reverse order, while doing binary search assuming ascending order.

Indeed, you do bubble only if

if (values[j + 1] > values[j])
{
}

Also, not that the last bubble you try to swap values[n-1] and values[n], but values[n] is beyond the limit.

1
  • Thanks, this fixed it :) I also had a problem with quitting early (condition n > 1 rather than n > 0 in the binary search). Jun 23 '17 at 19:04
1

Your while loop runs only when n > 1. You are not considering the case when there is just one element left for consideration and that is in fact the element to be searched for. So your code would give the correct answer only if the element to be found is not present in the array or if present then it is found before this case is reached.

For eg: Consider the case find 42 in {42, 43, 44}

Step 1:

min = 0, max = 2, mid = 1 & values[mid] > 42
Therefore, min = 0, max = mid - 1 i.e. max = 0


This is when your program exits since n = ((max - min) + 1) which makes n = 1 and thus the condition in the while loop becomes false.

Modify your code to handle this case and you're good to go :)

2
  • Also, binary search only works on a sorted array, so keep that in mind as well.
    – N. Tiwari
    Jun 23 '17 at 10:26
  • This was part of what was wrong, also had a problem with the bubble sort (it was sorting it backwards). Thanks :) Jun 23 '17 at 19:05

You must log in to answer this question.

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