4

int のソートされていない配列で指定されたターゲット値を見つける関数を C で書きたいとしましょう。一般に、これは単純で、O(n) 時間で実行されます。

int search(int *data, int len, int target)
{
    int i;
    for(i = 0; i < len; i++)
        if(data[i]==target) return i;
    return -1;
}

私たちがマゾヒスティックであり、代わりに分割統治アルゴリズムを使用してこれにアプローチしたいとしましょう。二分探索のように毎回配列の半分を除外できないため、再帰部分で問題が発生します。

int search(int *data, int start, int stop, int target)
{
// Base case: we've divided the array into two size subarray
    if(stop==start+1)
{
    if(data[start]==target) return start;
    if(data[stop]==target) return stop;
    return -1;
}
/* The recursion part is tricky.  
    We *need* to parse both halves of the array, because we can't safely
    exclude any part of the array; it's not sorted, so we can't predict
    which half it's going to be in.*/
else
{
    /** This obviously doesn't work. */
    int mid = (stop-start)/2;
    return search(data, start, mid, target);
    return search(data, mid+1, stop, target);
}
}

これを機能させる方法はありますか？

注: この質問を読んでいると思う人もいるかもしれませんが、これは私のために宿題をするように人々に求めているわけではありません。ただし、今週初めに提出した課題の問題を解決しようとしたときにこの問題に遭遇した後、好奇心に触発されました.

4

3 に答える 3

1

あなたの質問に対する答えはノーだと思います。データがソートされていない場合、バイナリ分割アプローチを使用しても何のメリットもありません。

于 2013-11-07T09:14:28.963 に答える
1

再帰呼び出しを次のように変更するのはどうですか:

else
{
    int mid = (stop-start)/2;
    int x = search(data, start, mid, target);
    if (x == -1)
        return search(data, mid+1, stop, target);
    else 
        return x;
}
于 2013-11-07T09:17:02.390 に答える