0

I got almost all of my code to work for find, it passes all of the check50s except 1, it finds 42 in {39, 40, 41, 43} My code so far is:

/**

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

include

include

include "helpers.h"

include

/** * Returns true if value is in array of n values, else false. */ bool search(int value, int values[], int n) { if (value < 0) { return false; } int low = values[0]; int high = values[n - 1]; int mid = (low + high) / 2; //printf("Low: %i Mid: %i High %i\n", low, mid, high); for (int i = 0; i < low + high; i++) {

    if (mid == value) {
        return true;
    }

    else if (mid < value) {
        low = mid + 1;
        mid = (low + high) / 2;
    }

    else {
        high = mid - 1;
        mid = (low + high) / 2;
    }
}
//printf("Low: %i Mid: %i High %i\n", low, mid, high);
 //TODO: implement a searching algorithm
return false;

}

/** * Sorts array of n values. */ void sort(int values[], int n) { int swapcount = 1;
//int iterations = 0; //int swapcount = 1; /if (n == 1) { return; }/

        for (int i = 0; i < n-1 ; i++) {
            if (values[i] > values[i + 1]) {
                printf("before swap %i, %i\n", values[i], values[i + 1]);
                int temp = values[i];
                values[i] = values[i + 1];
                values[i + 1] = temp;
                printf("after swap %i, %i,\n", values[i], values[i + 1]);
                swapcount++;
            }

            /*else {
                printf("Nothing to swap\n");
            }*/

            /*for (int j = 0; j < n; j++) {
                    printf("%i\n", values[j]);
            }*/
        }
        //return 0;
    if (swapcount == 1) {
        return;
        for (int j = 0; j < n; j++) {
            printf("Sorted array is %i", values[j]);
        }

    }

        //iterations ++;
        /*printf("%i Iterations\n", iterations);*/
        /*printf("Sorted is\n");
        for (int j = 0; j < n; j++) {
            printf("%i\n", values[j]);
        }*/
        //printf("Your swapcount is %i\n", swapcount);
        printf("%i swaps\n", swapcount);
        for (int w = 0; w < n; w++) {
            printf("array is %i\n", values[w]);
        }
        sort(values, n - 1);


// TODO: implement a sorting algorithm
//return;

}

0
int low = values[0];
int high = values[n - 1];
int mid = (low + high) / 2;

Why are your low/high/mid based on the values in the array, rather than their positions? A binary search should split the array in half each time. This split is based on the number of elements, not the values themselves. Otherwise, what might happen if the array is:

100, 10000, 20000, 30000, 88888

Your low is 100, your high is 88888, and your mid is then 44494

Can you see how those numbers are irrelevant?

Your high/lo/mid should be the positions in the array, not the values themselves, such that the mid in this case would be 2, so you'd be comparing value to values[2] to decide if you need to look left or right. And you'd adjust the low and high index values as needed.

It's only coincidental that you passed any of the check50 find tests, because the arrays given to you were sequential numbers. :)

| improve this answer | |

You must log in to answer this question.

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