获得一定范围内的对象与二进制搜索

我有这样一些数据：获得一定范围内的对象与二进制搜索

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

它们是对象（不是纯文本）。
我想获得ID = 2的所有对象。
我可以做一个二进制二进制搜索并获得索引3，但我怎么能得到（2和4）是否有任何有效的算法？
真正的问题有大约一百万件物品。

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

来源

2010-06-11 Behrooz

如果我理解正确，您的二分查找返回索引，其中将放置具有给定值的新元素。如果你只对索引范围感兴趣，那么当我的解决方案的每个id值很高时，这可能会更快。如果您需要这些值（不仅仅是索引范围）或每个ID值的数量很低，我的解决方案会更快一些。您的类型转换（整数到浮点数）可能会降低性能。 – 2010-06-11 11:07:15

你可以创建一个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。这终止了向上循环。

来源

2010-06-11 07:50:35

+1为我以前的解决方案，我正在做这样的事情，以避免使用map.my的目标是使用较少的内存和良好的性能。 – Behrooz 2010-06-11 07:52:59

你的回答帮助我回答了我自己。我会将其添加到原始问题中。 – Behrooz 2010-06-11 09:47:38

获得一定范围内的对象与二进制搜索

回答

相关问题