[解決済み] 重複を含むソート済み配列でのバイナリサーチの使用 [duplicate］

質問

私は、ソートされた配列の中で値xが見つかるすべてのインデックスを表示するメソッドを作成するように命じられました。

配列を0からN（配列の長さ）までスキャンするだけなら、実行時間は最悪の場合O(n)になることは理解しています。 メソッドに渡される配列はソートされているので、バイナリサーチを使えばO(log n)で済むので有利になると考えています。 しかし、これは配列が一意な値を持っている場合にのみ有効です。 バイナリサーチは、特定の値の最初の"find"で終了してしまうからです。 ソートされた配列からxを見つけるためのバイナリサーチを行い、このインデックスの前後の値をすべてチェックすることを考えていましたが、配列にすべてのxの値が含まれていた場合、それほど良い方法とは思えません。

私が聞きたいのは、ソートされた配列の特定の値に対するすべてのインデックスを見つけるのに、O(n)よりも良い方法はあるかということです。

public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
    // search through the sortedArrayOfInts

    // print all indices where we find the number 42. 
}

例：sortedArray = { 1, 13, 42, 42, 77, 78 } は次のように表示されます： "42 was found at Indices: 2, 3, 4" と表示されます。

どのように解決するのですか？

もし実際にソートされた配列があるなら、探しているインデックスの1つを見つけるまで2進法検索をすれば、そこから先はすべて隣り合っているので簡単に見つかるはずです。

最初のインスタンスが見つかったら、その前のインスタンスをすべて探し、さらにその次のインスタンスもすべて探します。

この方法だと、だいたい O(lg(n)+k) ここで k は、検索する値の出現回数です。

EDIT

そして、あなたは、すべてのアプリケーションにアクセスすることはできません。 k よりも小さい値で O(k) 時間です。

2回目の編集 そうすることで、実際に何か役に立つことをしていると感じられるからです。

Xの最初の出現と最後の出現を検索する代わりに、最初の出現のバイナリ検索と最後の出現のバイナリ検索を行うことができます。 O(lg(n)) その結果、すべてのインデックス間にXが含まれていることがわかります（ソートされていると仮定して）。

と等しいかどうかをチェックする検索を行うことで行うことができます。 x , AND と等しいかどうかを調べます。 x .