獲得一定範圍內的對象與二進制搜索

Question

我有這樣一些數據：

ID Value 
1 AAA 
1 ABC 
2 dasd 
2 dsfdsf 
2 dsfsd 
3 df 
3 dwqef 

它們是對象（不是純文本）。
我想獲得ID = 2的所有對象。
我可以做一個二進制二進制搜索並獲得索引3，但我怎麼能得到（2和4）是否有任何有效的算法？
真正的問題有大約一百萬件物品。

除bf和lisp之外的任何語言都可以提供幫助。

Answer 1

你可以創建一個Map來將一個id映射到一組值;

Map: 
1 => { AAA, ABC } 
2 => { dasd, dsfdsf, dsfsd } 
... 

這將有效的查找時間O（1）。您也可以執行二分查找，但查找效率較低。

二進制搜索算法：

首先創建一個排序列表（數組列表，鏈表等）。它必須在id上排序。然後你做一個標準的二進制搜索來找到一個匹配id的元素。然後你遍歷列表中的元素，直到元素與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。這終止了向上循環。