PSet 3: binary search help

Question

My program is almost working, I just cannot figure out why my binary search is not working. I am pretty sure that the sorting is fine. Any help would be appreciated.

check50:

:) 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}
:( 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}
:) doesn't find 42 in {39,40,41}
:) doesn't find 42 in {39,40,41,43}
:) finds 42 in {42,40,39,41}

my code:

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

#include <cs50.h>
#include <stdio.h>
#include <string.h>

#include "helpers.h"

const int MAXX = 65536;

bool binary_search(int value, int values[], int lo, int hi);

/**
 * 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
    int lo = 0;
    if (binary_search(value, values, lo, n)) {
        return true;
    } else {
    return false;
    }
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // TODO: implement a sorting algorithm
    if ( n > 1 ) {  // while haystack is greater than 1

        // counting sort, iterate through values[] and increment placement in hold[]
        int hold[MAXX];
        for (int i = 0; i < n; i++) {
        hold[values[i]]++;
        }

        // iterate through hold[] and place values back in sorted order in values[]
        int count = 0;
        for (int j = 0; j < MAXX; j++) {
            if (hold[j] > 0) {
                values[count] = j;
                count++;
                hold[j]--;  
            }

        }
    } else {
        return;
    }
    return;
}

bool binary_search(int value, int values[], int lo, int hi) {

    while (hi - lo > 0) {  // while search parameter is still positive

        // find the middle of the current array parameter
        int middle = (lo + hi) / 2;

        if (value == values[middle]) {  // if value is found return true
            return true;
        } else if (value > values[middle]) {  // if value is greater than the middle, set the lo to middle + 1, recursively
            lo = middle + 1;
            binary_search(value, values, lo, hi);
        } else if (value < values[middle]) {  // if value is less than the middle, set the hi to middle - 1, recursively
            hi = middle - 1;
            binary_search(value, values, lo, hi);
        } else {
            return false;  // if not found at all
        }

    }

    return false;  // if search parameter is negative, meaning value was not found

}

Answer 1

There are two problems with this code. First, while binary_search() calls itself recursively, it doesn't return the result. See http://cs50.stackexchange.com/questions/9691/pset3-binary-search-problems for detailed explanation.

Next, it has a problem when it gets to the end of the recursion under certain conditions. It is possible that the hi and lo values can be equal, but the code doesn't support this. ( was torn on whether to point this out directly or whether to give a hint, but it would be too complex. You should run it in debug to see what happens so that you understand. )

If this answers your questions, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)