次のようなデータがあります。
ID Value
1 AAA
1 ABC
2 dasd
2 dsfdsf
2 dsfsd
3 df
3 dwqef
それらはオブジェクトです（プレーンテキストではありません）。
ID = 2 のすべてのオブジェクトを取得したいのです
が、バイナリ バイナリ検索を実行してインデックス 3 を取得できますが、(2 と 4) を取得するにはどうすればよいですか? 効率的なアルゴリズムはありますか?
本当の問題は、約 100 万項目のリストです。
bf と lisp 以外のどの言語でも役に立ちます。
ID を値のコレクションにマップする Map を作成できます。
Map:
1 => { AAA, ABC }
2 => { dasd, dsfdsf, dsfsd }
...
これにより、効率的なルックアップ時間が O(1) になります。二分探索もできますが、ルックアップの効率は低下します。
二分探索アルゴリズム:
まず、ソートされたリスト (arraylist、linkedlist など) を作成します。IDでソートする必要があります。次に、標準のバイナリ検索を実行して、id に一致する要素を 1 つ見つけます。次に、要素が id と一致しなくなるまで、リストを上下にトラバースします。これにより、指定された ID を持つすべてのオブジェクトが検索されます。
リストの例:
List Index, Object
0 Id=1 Value=A
1 Id=2 Value=B
2 Id=2 Value=C
3 Id=3 Value=D
4 Id=3 Value=E
二分探索はインデックス 2 を返します。下向きのループでは、最初に一致する要素 1: Id=2 が検出され、次に要素 0: Id=1 が一致しないため、下向きのループが終了します。上向きのループは、一致しない要素 3: Id=3 を最初に見つけます。これにより、上向きのループが終了します。