c - Cでの二分探索の分割と征服

Question

私はバイナリ検索の分割統治バージョンを作成しようとしていますが、配列を2つのサブ配列に分割し、マージソートでのマージに似た検索を行うものです。これは、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、配列には存在しません。結果は正しいです。おそらくパラメータをめちゃくちゃにしただけです。最初のパラメータは配列、次の2つは検索範囲を表し、4つ目は探しているものです。正しい呼び出しは次のようになります。

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))

Answer 2

まだ解決策を探している人のために、これは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;
}

Answer 3

配列にないキー99を指定したので、コードが-1を返すことは明らかです。