这个二分查找函数有什么问题吗？
我正在尝试解决二分搜索的 Spoj 问题，但我不断得到“错误答案”，而且我看不到我的问题。 这是我的 bsearch 函数：
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;
}
这是我的主要函数
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;
}
这是 SPOJ 问题： http://www.spoj.com/problems/BSEARCH1/
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/
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
问题是您需要返回第一次出现的位置（从零开始），并且一旦找到密钥就返回。
但数组可能是：
0 1 1 1 1 1 1 1 1 1 1 1 2
键为 1。您应该返回 1（第一次出现的位置），但实际上返回了 6。
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.
你的算法是正确的。数据未排序，因此二分搜索算法无法正确地将解决方案归零。
Your algorithm is correct. The data is not sorted, so you binary search algorithm cannot correctly zero in on the solution.
不完全清楚您正在使用哪种基于 C 的语言，但表达式 (end - start)/2 可能会返回一个浮点值，然后当您实际上希望该值四舍五入时该浮点值被截断为整数？
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?