整数の配列を考えてみましょう (ソートされていると仮定します)。指定された整数に最も近い整数の配列インデックスを可能な限り最速の方法で見つけたいと思います。複数の可能性がある場合、アルゴリズムはすべてを識別します。
例: T=(3, 5, 24, 65, 67, 87, 129, 147, 166) を考えます。指定された整数が 144 の場合、コードは 147 を最も近い整数として識別し、配列インデックス 7 を指定する必要があります。そのエントリに対応します。66 の場合、アルゴリズムは 65 と 67 を識別する必要があります。
これを行うための O(1) または少なくとも O(log N) アルゴリズムはありますか? 直接検索アルゴリズム (バイナリ検索、ツリー検索、ハッシングなど) の実装は、完全な一致が必要になるため機能しません。これらを修正して近似検索を処理する方法はありますか?
私はCコードを開発しています。
ありがとう