0

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

3 回答 3

3

这很简单，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))二进制搜索解决方案。

于 2012-05-28T13:28:24.090 回答
1

对于仍在寻找解决方案的任何人，我发现这是由ankzcode.

它使用分治法在没有线性搜索的情况下找到数组中的最小值。

#include <stdio.h>

int findMin(int a[], int l,int h)
{
    int pivot = (l + h) / 2;
    int minl=-1, minh = -1;

    if ( (pivot - l ) > 1) 
    {
        minl = findMin(a, l, pivot);
    }
    else 
    {
        minl = (a[l] > a[pivot])?a[pivot]:a[l];
    }
    if ( (h - pivot ) > 1) 
    {
        minh = findMin(a, pivot, h);
    }
    else 
    {
        minh = (a[l] > a[pivot])?a[pivot]:a[l];
    }

    return (minl>minh)?minh:minl;
}

int main()
{
    int a[]={5,2,9,10,3};
    printf("%d\n",findMin(a, 0, 5));
    return 0;
}
于 2012-11-12T07:55:30.263 回答
0

你给了键 99，它不在数组中，所以很明显代码返回 -1。

于 2012-05-28T13:30:33.347 回答