c - C における配列の問題

Question

シフトされた配列が与えられた場合 (例):

[17 34 190 1 4]

からシフトした（オリジナルはわかりません）

[1 4 17 34 190]

その数の位置を見つけるための良い関数は何でしょうか?

たとえば、1 を渡すと、3 番目の位置が返されます。

Answer 1

答えの線形検索は常に機能しますが、O(log) 時間でそこに到達できると思います。

シフトソートされた配列の値が想定に反するかどうかを確認することによる、シフトポイントのある種のバイナリ検索。トライを作成するようなものです。「不正な」ノードが見つかるまで、ソートされたツリーを形成し続けます (これは多くの詳細をごまかしています - 私は知っています)。これにより、変曲点がどこにあるかがわかるため、配列を 2 つの並べ替えられたベクトルとして扱うことができます。検索する値がそれぞれの最大エントリよりも大きいかどうかをすばやく確認して、検索するベクトルがわかるようにします。Bソートされたベクトルで値を検索し、そのインデックスを返す。

難しい部分は、変曲点を見つけることです。:)

Answer 2

アレイをスキャンする必要があります。

size_t pos_in_arr(int *arr, size_t arr_size, int match)
{
    size_t i;
    for (i = 0; i < arr_size; i++)
        if (arr[i] == match)
            break;
    return i;
}

この関数は、要求された位置を返すか、要素が見つからない場合は最大位置より 1 つ多い位置を返します。

解決策はあなたが求めるものですが、配列がシフトされたという事実をまったく使用しないため、おそらく必要なものではありません。元の問題はもっと複雑だと思います。

たとえば、元の配列の 1 つの要素が 5 番目で、現在は 7 番目であり、探している要素が 23 番目であることがわかっている場合、実際に配列を 25 番目までスキャンせずに「25 番目」と答えることができます。これは、エクササイズ全体のポイントになる可能性があります。しかし、そのようなソリューションを構築するには、問題についてもっと知る必要があります。