c - C中的分而治之二分查找

Question

我正在尝试制作分而治之的二进制搜索版本，但是将数组划分为两个子数组并进行类似于合并排序中的搜索的搜索，我想这样做的原因是因为我想在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;
    }
}

Answer 1

很简单，99 不存在于您的数组中。结果是正确的。您可能只是弄乱了参数 - 第一个是数组，接下来的两个代表搜索范围，第四个是您要查找的内容。正确的调用是:

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

还有这个

int* A = &a[0];

没用，您可以简单地使用 a 作为数组衰减为指针:

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

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

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