获得一定范围内的对象与二进制搜索
问题描述:
我有这样一些数据:获得一定范围内的对象与二进制搜索
ID Value
1 AAA
1 ABC
2 dasd
2 dsfdsf
2 dsfsd
3 df
3 dwqef
它们是对象(不是纯文本)。
我想获得ID = 2的所有对象。
我可以做一个二进制二进制搜索并获得索引3,但我怎么能得到(2和4)是否有任何有效的算法?
真正的问题有大约一百万件物品。
除bf和lisp之外的任何语言都可以提供帮助。
答
你可以创建一个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。这终止了向上循环。
如果我理解正确,您的二分查找返回索引,其中将放置具有给定值的新元素。如果你只对索引范围感兴趣,那么当我的解决方案的每个id值很高时,这可能会更快。如果您需要这些值(不仅仅是索引范围)或每个ID值的数量很低,我的解决方案会更快一些。 您的类型转换(整数到浮点数)可能会降低性能。 – 2010-06-11 11:07:15