search - 使用二分搜索获取一系列对象

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

您可以创建一个将 id 映射到值集合的 Map；

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

这将具有 O(1) 的有效查找时间。您也可以进行二进制搜索，但查找效率会降低。

二分查找算法：

首先，您创建一个排序列表（arraylist、linkedlist 等）。它必须按 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。这终止了向上循环。