マージソートを変更してソートせずに要素のインデックスを返す方法

Question

配列をソートせずに再帰的に特定の要素のインデックスを取得する方法はありますか？

Answer 1

ブルートフォース検索と再帰検索の両方がこの場合、同じ時間複雑さを持ちます。あなたは再帰的なバージョンをしたい場合はしかし、まだ、その後の擬似コードはです：

1. は、配列の静的インデックスをsearch.Initする配列やキーで関数を呼び出します。インデックスが範囲外にある場合、戻り-1（見出されないことを意味する）

2. チェック

3. チェックアレイ内の現在の要素がキーである場合。 trueの場合は静的インデックスを返します。

4. 他の場合は、インデックスをインクリメントして関数呼び出しを返します。

Answer 2

おそらく、ソートされたリストの特定の要素のランクを見つけることを指しています。

実際には、この操作では配列を明示的にソートする必要はなく、単純にいくつの要素が小数点以下であるかをカウントします（昇順ソートの場合）。

それぞれの要素をチェックする必要があるため、可能な限り複雑なのはO（n）です。

非再帰的アプローチを使用して単純にO（n）の複雑さを達成するのは簡単です。単純にすべての要素を反復処理し、小さな要素に遭遇するたびにカウンタを増やします。カウンタの最終値は、ソートされた配列内の対象要素の位置を示します（これは明示的にソートせずに取得されたことに注意してください）。 （Cスタイルのコードを使用して）以下に例示するこの動作を模倣する

単純な再帰ソリューション：

getRank(int value, int* array, int nElements) { 
    if (nElements == 0) return 0; 

    if (array[0] < value) 
     return 1 + getRank(value, array + 1, nElements - 1); 
    else 
     return getRank(value, array + 1, nElements - 1); 
}