0

My code seems to work fine for binary search, checking the sorted list looks good and code passes check50. Needle is found in more limited searches (like ./ generate 500) but will not find needle in 1000? Cannot figure out what is wrong?

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


{
int low = 0;
int high = n;
int mid;

if (value > values[n-1])
{
    // no need to look any further
    return 0;
}
while (values[low] < values[high])
// keep checking while
{
    mid = (low + high) / 2;
    if (value > values[mid])
    // discard left half of array, make new low and restart search
    {
        low = mid + 1;
    }
      else if ((value == values[mid]) || (value == values[low]) || (value == values[high]))
    // if value is either exactly mid or both ends
    {
        // found it
        return 1;
    }      
    else if (value < values[mid])
    // discard right half of array, make new high and restart search
    {
        high = mid - 1;
    }       

}
// exit if all else fails
return 0;

}



/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
// TODO: implement an O(n^2) sorting algorithm: selection sort
// using a temporary buffer called temp. sorts ascending
int min, temp, i, j;

if (n < 1)
// if there is no real list
{
    return;
}

for (i = 0; i < (n - 1); i++)
{
    min = i;
    for (j = (i + 1) ; j < n; j++)
    // when found a smaller number make that smallest number
    {
        if (values[j] < values[min])
        {
            min = j;
        }
    }
    if (min != i)
    // if found smaller nummer and swap
    {
        temp = values[i];
        values[i] = values[min];
        values[min] = temp;
    }
}
// DEBUG code to see sorted list
for ( int k = 0; k < n; k++)
{
    printf("no %i : %i\n", k , values[k]);
}
return;
}
0

You have two issues here, both in your search function. First, there's a problem with the initial value of high. You're setting high= n, which means that it is trying to access one element beyond the end of the values array. Remember, n elements means that the last element is n-1. This is really killing your search routine. Fixing this resolves most of the problems, but it still fails when the last element is the needle (and maybe other cases too.)

Second is a logic error. In your while loop, you have a sequence of if/else if/else if. The middle block, else if ((value == values[mid]) || (value == values[low]) || (value == values[high])) depends on the current state of values[mid] being tested. Unfortunately, the first if block may have already altered that value, invalidating the test (meaning it's testing the wrong value array element). IF you swap the first and second if code blocks, the values[mid] remains intact and it should resolve your problems.

There may be more issues (not likely), but this should get you going.

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

2
  • BTW, you can test with needle = 42 and list = 40, 41, 42 to produce the problems.
    – Cliff B
    Feb 11 '16 at 18:12
  • Yes, that totally solved it. Thanks! The n and n-1 part I tried and changed and tried again before; knew that but it did not seem to help...switching the if statement did it and made the n-1 work too. stupid to have overseen that one ;) Makes so much sense. Big learning event...will never forget to check the right order of the if's!
    – Inge
    Feb 12 '16 at 20:35

You must log in to answer this question.

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