# search and sort seem to work but cannot find needle in large haystack?

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;
}
``````

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.