並べ替えられていないシーケンス内の指定された数よりも大きい最初の数を見つける

Question

正の整数のシーケンスと整数Mが与えられた場合、Mよりも大きいシーケンスの最初の数字を返します（存在しなければ-1） 。

例：配列= [2、50、8、9、1]、M = 3 - （前処理した後に）必要な各クエリの>リターン= 50

O（ログn）。

私は私にO（LOGN）の時間を与えないとだけ長いパスを、取得したい...

EDIT分探索木と思ったが、昇順を与えてくれた

：使用される構造にもする必要がありますつまり、見つかった要素を与えられた要素に置き換えることができ、別のM（すべてのもの - 前処理 - O（logn）とは別に）の検索を繰り返すことが可能でなければなりません。もちろん、最初の大きい方を最初の小さい方に変更でき、アルゴリズムをあまり変更しなくてもいいといいですね。それが助けになると、すべての数字が正で繰り返しがないと仮定することがあります。

Answer 1

各要素に対して、i：aux[i] = max { arr[0],arr[1], ... ,arr[i]}（元の配列の添字がj <= iの最大要素）の2番目の配列を作成します（auxとします）。

この配列は本質的にソートされていることが分かりやすく、auxの単純なbinary searchは必要なインデックスを生成します。 （要素が存在しない場合は、要求された要素よりも大きい最初の要素をバイナリ検索で取得するのは簡単です）。

時間複雑度は、前処理（1回のみ実行）およびO(logn) /クエリです。