0

so currently doing pset3 & i think my sort function is all good (i've printf'd each value & it's all in the right order), but when trying to implement binary search it's failing half the tests for whatever reason!

Here's the code:

perhaps the exit condition is wrong i'm not sure !

Here's the check 50:

:) 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}

:( finds 42 in {40,41,42,43} \ expected an exit code of 0, not 1

:( 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

include

#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)
{
    // base case to make sure user has put in a string which is greater than 0.
    while (n > 0)
    {

        int min = 0;
        int max = n - 1;
        int k = (max - min)/2;
        // looking to utilize this loop to use m value to define bounds of inspection.
        for (int m = 0; m <= n/2; m++)
        {
            if (m == n/2)
            {
                return false;
            }
            if (values[(max - min)/2] == value)
            {
                return true;
            }
            else if (values[(max - min)/2] < value)
            {
                min = k + 1;
            }
            else if (values[(max - min)/2] > value)
            {
                max = k - 1;  
            }
        }
    }    
    return false;
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{

   for (int i = 0; i < n - 1; i++)
   {
       // cycling through each pair
       for (int j = 0; j < n - 1 - i; j++)
       {

            if (values[j] > values[j + 1])
            {
                int temp = values[j];
                values[j] = values[j + 1];
                values[j + 1] = temp;
            }

        }

   }
   printf("\n");

   // printing code
   for (int k = 0; k < n; k++)
   {
       printf("values[%i] = %i \n", k, values[k]);
   }

}

1 Answer 1

0

Well, it is not binary search. In binary search, each time you divide values[] by two, choose one part, forget about the other, and repeat. Meanwhile, you divide just one time, then continue checking both part one by one.

Your code may be corrected a bit and it will finally do the job, but instead, in my opinion, you need to rethink the algorithm to make it true binary search.

You must log in to answer this question.

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