C中除和二进制搜索(divide and conque binary search in C)

我试图划分和征服二进制搜索的版本，但是将数组划分为两个子数组并且搜索类似于合并排序中的合并，我之所以这样做是因为我想在cilk中使用它，但是我必须这样做。这是我写的代码，它似乎有一些错误，因为它返回-1到有效的键值。

#include <stdio.h> #include "BinarySearch.h" int main () { int a[] = {0,1,2,3,4,5,6,7,8,9}; int index = binarySearch(a, 0, 9, 7); printf("%i", index); return 0; } int binarySearch (int* A, int first, int last, int key) { if (last < first) return -1; else { int mid = (last + first) / 2; if (A[mid] == key) return mid; int x, y; x = binarySearch(A, first, mid - 1, key); y = binarySearch(A, mid + 1, last, key); if (x == -1 && y == -1) return -1; else if (x == -1 && y != -1) return y; else return x; } }

I'm trying to make a divide and conquer version of binary search, but one that divides the array to two subarrays and search similar to merging in merge sort, the reason I want to do that becuase I want to use it in cilk, but I have to make it that way. Here is the code I wrote, which seems to have something wrong with it as its returning -1 to valid key values.

#include <stdio.h> #include "BinarySearch.h" int main () { int a[] = {0,1,2,3,4,5,6,7,8,9}; int index = binarySearch(a, 0, 9, 7); printf("%i", index); return 0; } int binarySearch (int* A, int first, int last, int key) { if (last < first) return -1; else { int mid = (last + first) / 2; if (A[mid] == key) return mid; int x, y; x = binarySearch(A, first, mid - 1, key); y = binarySearch(A, mid + 1, last, key); if (x == -1 && y == -1) return -1; else if (x == -1 && y != -1) return y; else return x; } }

最满意答案

很简单，你的数组中不存在99 。结果是正确的。你可能只是弄乱了参数 - 第一个是数组，接下来的两个代表搜索的范围，第四个是你正在寻找的范围。正确的电话会是：

int index = binarySearch(A, 0, 10, 4);

还有，这个

int* A = &a[0];

是没用的，你可以简单地使用a数组衰减到指针：

int index = binarySearch(a, 0, 7, 99); // a instead of A

此外 - 二进制搜索考虑了数组已排序的事实。如果您的密钥低于中间值，为什么还要向右搜索 - 这保证您不会在那里找到它。

你正在做的是O(n) ，而不是O(log(n))二进制搜索解决方案。

It's simple, 99 doesn't exist in your array. The result is correct. You probably just messed up the parameters - the first one is the array, the next two represent the range of the search, the fourth one is what you're looking for. A correct call would be:

int index = binarySearch(A, 0, 10, 4);

Also, this

int* A = &a[0];

is useless, you can simply use a as arrays decay to pointers:

int index = binarySearch(a, 0, 7, 99); // a instead of A

Also - a binary search takes into account the fact that the array is sorted. If your key is lower than the middle value, why bother searching to the right - it's guaranteed you won't find it there.

What you're doing is O(n), as opposed to a O(log(n)) binary search solution.

更多推荐