ここに状況があります。私は、特定のミリ秒で解雇される必要のあるイベントを表すソートされた整数のリストを持っています。私は、一般的に前方100msごとに移動しますが、ランダム追求し、同様に後方スクラブ前方とすることができplayheadを持って整数リストの中で最も近い整数を見つけるための効率的なアルゴリズムを探してください
0
1500
5000
9348
89234
109280
109281
109283
150000
：このリストは、次のようになります。その再生ヘッドは100の倍数であることは保証されていませんが、実際の問題なしにその倍数にフロアすることができます。
私の挑戦は、現在の再生ヘッド以下のリスト内の最も近い要素を効率的に見つけることです。リストの平均長は300〜1500エレメントです。私は設定された間隔でかなり容易にフォワードを最適化することができますが、ランダムシークはもう少し複雑です。
私はアルゴリズムクラスで眠っていませんか？
私はDivide and conquer algorithmがベストスーツだと思います。
変更されたバイナリ検索が必要なようです。リストはソート順であるため、バイナリ検索では線形検索よりも検索パフォーマンスが大幅に向上し、配列内の項目の間隔についてわからない場合はバイナリ検索よりもはるかに優れていません。あなたが平等を探しているわけではないので、バイナリ検索はわずかに変更する必要がありますが、それ以上のことはありません。
var testData = [0,1500,5000,9348,89234,109280,109281,109283,150000];
function findNearest(data, val) {
if (!data || !data.length) {
return(null);
}
var lowest = 0, mid;
var highest = data.length - 1;
while (true) {
if (lowest == highest) {
return(lowest);
}
mid = Math.ceil(((highest - lowest)/2) + lowest);
if (data[mid] == val) {
return(mid);
}
else if (data[mid] < val) {
lowest = mid;
} else {
highest = Math.max(lowest, mid - 1);
}
}
}
は、ここでそれだけで一つの要素にまでなるまで（上半分または下半分の試験値との比較に基づいて、各時間一緒に行く）1/2に検索データを分割し続ける実際のアルゴリズムです
そして、作業テストプログラム：http://jsfiddle.net/jfriend00/rWk2X/
注：このコードは、アレイ内のすべての値がソート順序であるとみなし、アレイが空ではありません。
ターゲット値よりも小さい値を持たない配列を与えると、配列の最初の値が常にターゲットよりも小さいことを確認しない限り、扱う必要のある特殊なケースである0が返されます値（例えば、常にゼロ）。
ターゲット値より大きい値を持たない配列を与えると、配列内の最後の値が返されます（これは必要なものです）。これは特別な場合ではなく、必要な答えです。
これは面白いアルゴリズム問題のように思えましたので、私は答えに実用的なコード例を追加しました。これで遊ぶならば、無限ループを起こすのはとても簡単なので注意してください。私は実際に無限ループを避けるために、テスト中に最大回数の繰り返しを自分のコードにコード化しました（これはエラーが発生した1000回の繰り返し後に中断します）。 – jfriend00
これは最善の解決策のようです。無限ループにつながる特定の入力セットがありますか？ – turing1
@入力 - 無限ループは発生しません。あなたは何かを渡すことができますし、コードの後にコメントとして説明するとうまく処理されます。あなたが関数内のコードを混乱させ、それを実行した場合に限り、無限ループの危険性があります。 – jfriend00
ソートされたリストなので、バイナリ検索を使用します。あなたはもっとうまくいくかもしれませんが、あなたはさらに別の仮定を払わなくてはなりません（例えば、私はそうは思わない数字の分布を仮定しなければなりません）。あなたはそれについてここで読むことができます：http://en.wikipedia.org/wiki/Binary_search_algorithm
私はその問題に直前に直面し、いくつかの実行時間の比較を行いました。
hereをご覧ください。 （サンプルはIEでは動作しません）
第4の実装は、ダムバイナリ検索と比べて本当にルールに近いようです。
希望します。
bye
最も簡単な方法：配列を逆方向にループし、再生ヘッド以下の最初の要素を選択します。これを試しましたか？これはあなたのユースケースではあまりにも非効率的ですか？ – deceze
課題は効率的に見つけることです...直線検索は効率的ではありません。 –
でも十分に*効率的かもしれません。現代の機械では1500要素はそれほど多くありません。 – deceze