私は最近インタビューの質問を与えられました.あなたは数字の順序付けられたリストを持っており（要素の数は100000のオーダーで非常に大きくなる可能性があります）、与えられた数よりも大きい最小の数を見つけなければならないとします. O(log n) 時間...私の最初の推測では、インタビュアーが「はい」と言ったツリーのようなデータ構造を使用していましたが、これらのツリーを構築するオーバーヘッドがあり、別の方法を提案できますか? 私の明白な答えは、配列を使用したバイナリ検索でしたが、それが機能するかどうか、または他に何かあるかどうか疑問に思っていましたか?
質問する
1466 次
1 に答える
0
使用しているリストのタイプによって異なります。
インデックス付きリストではない場合、再構築なしでは O(logN) は不可能です。
したがって、インデックス付きリストの場合。
割り算で検索できます。
ターゲットを a[n/2] と比較する
a[n/2] がターゲットよりも小さい場合..検索スペースが縮小されます。a[n/2+1]..a[n-1]から開始
a[i] < target < a[i+1] のようなペアが見つかるまで、同じアプローチで再帰アルゴリズムを使用します。
これで終わり、a[i+1] があなたの答えです..!!
于 2013-03-30T23:09:20.843 に答える