Reputation: 930
I am tring to solve a Spoj problems of Binary Search but I keep getting "wrong answer" and I can't see my problem. Here is my bsearch function:
int binarySearch(int numbers[], int size, int key)
{
int start = 0;
int end = size - 1;
int middle;
while(start <= end)
{
middle = start + (end - start)/2;
if(key < numbers[middle])
end = middle - 1;
else if(key > numbers[middle])
start = middle + 1;
else
return middle;
}
return -1;
}
And this is my main function
int main()
{
int *numbers;
int n_numbers, n_queries, key, i, found;
scanf("%d %d", &n_numbers, &n_queries);
numbers = (int*)malloc(n_numbers * sizeof(int));
for(i = 0; i<n_numbers; i++)
scanf("%d", &numbers[i]);
for(i = 0; i<n_queries; i++)
{
scanf("%d", &key);
found = binarySearch(numbers, n_numbers, key);
printf("%d\n", found);
}
return 0;
}
Here is the SPOJ problem: http://www.spoj.com/problems/BSEARCH1/
Upvotes: 0
Views: 601
Reputation: 9490
The problem is that you are required to return the location of the first occurrence (starting from zero), and you are returning as soon as you find the key.
But it's possible that the array is: 0 1 1 1 1 1 1 1 1 1 1 1 2
And the key is 1. You should return 1 (the location of the first occurence) and instead you are returning 6.
Upvotes: 3
Reputation: 491
Not totally clear which C based language you are using but might the expression (end - start)/2 possibly return a floating point value that is then truncated to an integer when you actually would want the value rounded?
Upvotes: 0
Reputation: 24336
Your algorithm is correct. The data is not sorted, so you binary search algorithm cannot correctly zero in on the solution.
Upvotes: 1