10、25、36、43 ....、118、121（ソートされた数値）のような20個の数値（64ビット整数）の配列があります。
今、私は入力として何百万もの数字を与えなければなりません（例えば17、30）。
私が出力として与えなければならないのは：
for Input 17:
17 is < 25 and > 10. So, output will be index 0.
for Input 30:
30 is < 36 and > 25. So, output will be index 1.
今、私は線形探索、バイナリ検索を使用してそれを行うことができます。より速くそれを行う方法はありますか？入力番号はランダム（ガウス）です。
分布を知っている場合は、よりスマートな方法で検索を指示できます。
バイナリ検索のこのバリアントの大まかなアイデアは次のとおりです。
データが0〜100で均一に分散されると予想されると仮定します。
値0を観察すると、最初から開始します。値が37の場合、配列の37％から開始します。これが二分探索との主な違いです。常に50％から開始するわけではありませんが、期待される「最適な」位置から開始しようとします。
これは、パラメーターがわかっている場合はガウス分布データでも機能します（パラメーターがわからない場合でも、観測データから簡単に推定できます）。ガウスCDFを計算すると、検索を開始する場所が得られます。
次のステップでは、検索を絞り込む必要があります。あなたが見た位置では、異なる値がありました。これを使用して、位置を再推定し、検索を続行できます。
これで、ディストリビューションがわからなくても、これは非常にうまく機能します。したがって、二分探索から始めて、すでに50％と25％のオブジェクトを調べました。次に37.5％に進む代わりに、クエリ値がたとえば50％エントリに非常に近い場合は、より適切な推測を行うことができます。データセットが非常に「不器用」でない限り（そしてクエリがデータに相関していない場合）、これは常に中央で分割される「ナイーブ」なバイナリ検索よりも優れているはずです。
http://en.wikipedia.org/wiki/Interpolation_search
予想される平均実行時間はO(log(log(n))、ウィキペディアからのようです。
更新：誰かがたった20の数字で物事が違うと不平を言ったので。はい、そうです。20の数値では、線形探索が最適な場合があります。CPUキャッシングのため。CPUキャッシュに収まる少量のメモリを介した線形スキャンは非常に高速です。特に展開されたループの場合。しかし、その場合は非常に哀れで面白くない私見です。
私はあなたにとって最良の選択肢はupper_boundを使用することだと信じています-それはあなたが探しているものよりも大きい配列の最初の値を見つけるでしょう。
それでも、解決しようとしている問題によっては、lower_boundまたはbinary_searchが必要な場合があります。
これらのアルゴリズムはすべて、対数的に複雑です。
binary search配列がソートされているので、これ以上良いものはありません。
線形探索はO(n)二分探索がO(log n)
編集：
補間検索は、追加の仮定を行い（要素は均一に分散されている必要があります）、反復ごとにより多くの比較を行います。
両方を試して、どちらが自分のケースに適しているかを経験的に測定することができます
実際、この問題は非常に興味深いものです。なぜなら、それは情報理論のフレームワークを再構築したものだからです。
20 個の数値が与えられると、最終的に 21 個のビンになります (< 最初のものと > 最後のものを含む)。
着信番号ごとに、これらの 21 個のビンの 1 つにマップします。このマッピングは比較によって行われます。比較ごとに 1 ビットの情報が得られます (< または >= -- 2 つの状態)。
したがって、入ってくる数値がどのビンに属しているかを判断するために 5 回の比較が必要だとすると、その数値を表すために 5 ビットを使用することと同じになります。
私たちの目標は、比較の数を最小限に抑えることです! それぞれが 21 の順序付けられたコード ワードに属する 100 万の数字があります。どうやってそれを行うのですか？
これはまさにエントロピー圧縮の問題です。
a[1]、.. a[20] を 20 の数字とします。
p(n) = pr { 着信番号は < n } とします。
次のように決定木を構築します。
Step 1.
let i = argmin |p(a[i]) - 0.5|
define p0(n) = p(n) / (sum(p(j), j=0...a[i-1])), and p0(n)=0 for n >= a[i].
define p1(n) = p(n) / (sum(p(j), j=a[i]...a[20])), and p1(n)=0 for n < a[i].
Step 2.
let i0 = argmin |p0(a[i0]) - 0.5|
let i1 = argmin |p1(a[i1]) - 0.5|
等々...
完了するまでに、次のようになります。
i, i0, i1, i00, i01, i10, i11, etc.
これらの i のそれぞれが、比較位置を示します。
したがって、アルゴリズムは次のようになります。
u = 入力番号とする。
if (u < a[i]) {
if (u < a[i0]) {
if (u < a[i00]) {
} else {
}
} else {
if (u < a[i01]) {
} else {
}
}
} else {
similarly...
}
したがって、i はツリーを定義し、if ステートメントはツリーを歩いています。ループに入れることもできますが、if を使って説明する方が簡単です。
たとえば、データが 0 から 2^63 の間で一様に分布していることがわかっていて、20 の数が
0,1,2,3,...19
それから
i = 20 (notice that there is no i1)
i0 = 10
i00 = 5
i01 = 15
i000 = 3
i001 = 7
i010 = 13
i011 = 17
i0000 = 2
i0001 = 4
i0010 = 6
i0011 = 9
i00110 = 8
i0100 = 12
i01000 = 11
i0110 = 16
i0111 = 19
i01110 = 18
基本的に、比較は次のようになります。
if (u < a[20]) {
if (u < a[10]) {
if (u < a[5]) {
} else {
...
}
} else {
...
}
} else {
return 21
}
ここで、二分探索を行っていないことに注意してください。私は最初に終点をチェックしています。なぜ？
100*((2^63)-20)/(2^63)% の確率で a[20] より大きくなります。これは基本的に 99.999999999999999783159565502899% の確率です!
したがって、このアルゴリズムでは、上記で指定されたプロパティを持つデータセットの予想比較数は 1 です。(これは log log :p よりも優れています)
ここで行ったことに注意してください。基本的に、可能性の高い数値を見つけるために少ない比較を使用し、可能性の低い数値を見つけるために多くの比較を使用していることに注意してください。たとえば、数値 18 には 6 回の比較が必要です (二分探索の場合よりも 1 回多い)。ただし、20 から 2^63 までの数値は 1 回の比較しか必要ありません。これと同じ原理がロスレス (エントロピー) データ圧縮に使用されます。頻繁に現れるコード ワードをエンコードするために、より少ないビットを使用します。
ツリーの構築は 1 回限りのプロセスであり、100 万回後にツリーを使用できます。
問題は...この決定木が二分探索になるのはいつですか? 宿題の練習！:p 答えは簡単です。これは、ファイルを圧縮できなくなった場合と似ています。
わかりました、だから私はこれを私の後ろから引き出しませんでした...基礎はここにあります:
std::lower_boundとstd:: upper_boundを使用してバイナリ検索を実行できます。これらはイテレータを返すのでstd::distance、インデックスを取得するために使用できます。