0

(キーまたは最も近い一致 (上限)) の最後の出現を検索するための効果的なアルゴリズムを実装しています。

これまでのところ、私はこれを手に入れました。

long bin_search_closest_match_last_occurance ( long  * lArray, long sizeArray, long lnumber)
{
    long left, right, mid, last_occur;

    left = 0;
    right = sizeArray - 1;
    last_occur = -1;

    while ( left <= right )
    {
        mid = ( left + right ) / 2;

        if ( lArray[mid] == lnumber  )
        {
            last_occur = mid;
            left = mid +1;
        }

        if ( lArray[mid] > lnumber ) 
            right = mid - 1;
        else 
            left = mid + 1;
    }
    return last_occur!=-1?last_occur:mid;
}

配列を持ってみましょう{0,0,1,5,9,9,9,9}。キーは6 Fce が index を返す必要があり7ますが、私の fce は返します4

最後に一致するインデックスまで線形に反復したくないことに注意してください。

念頭に置いて、パラメーター fce(開始、終了インデックスを追加) を変更し、見つかった上限から配列の最後まで fce を使用して別のバイナリ検索を実行するソリューションがあります (正確な一致が見つからない場合のみlast_occur==-1)。

それを実装するためのより良い/よりクリーンなソリューションがあるかどうかを尋ねたいですか?

4

1 に答える 1

0

nm の 2-search アプローチは機能し、最適な時間の複雑さを維持しますが、最初の検索が終了した場所から 2 番目の検索を開始すると、定数係数が約 2 倍、または約 1.5 倍になる可能性があります。

代わりに、 (または、存在しない場合は下限)の最初のインスタンスを見つける「通常の」二分探索を行い、それを変更して、アルゴリズムがすべての配列アクセスを変更して配列を論理的に「反転」するようにします。 (任意の式に対して)、また、テストをに変更して順序を「逆」にすると、単一のバイナリ検索のみが必要になります。このアルゴリズムが実際に実行する唯一の配列アクセスは、 への 2 つのルックアップであり、最適化コンパイラは、アクセスの間に値が何も変更されないことが証明できる場合、1 回だけ評価する可能性が非常に高くなります (これには、の宣言に追加する必要がある場合があります)。lnumberlArray[x]lArray[sizeArray - 1 - x]x> lnumber< lnumberlArray[mid]restrictlong * lArray; または、要素をローカル変数にロードして、代わりに 2 回テストすることもできます)。いずれにせよ、反復ごとに 1 つの配列ルックアップのみが必要な場合、インデックスを からmidに変更すると、反復ごとに 2 つの余分な減算が追加されます (または、ループに入る前のsizeArray - 1 - mid場合は 1 つだけ)。 --sizeArraynmのアプローチと同じくらい。もちろん、他のことと同様に、パフォーマンスが重要な場合はテストしてください。そうでない場合は、マイクロ秒の節約についてあまり心配する必要はありません。

また、戻り値も「逆にする」必要があります。

return last_occur!=-1?last_occur:sizeArray - 1 - mid;
于 2014-11-25T14:26:05.283 に答える