получить диапазон объектов с помощью бинарного поиска

Question

У меня есть такие данные:

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

это объекты (не простой текст).
и я хочу получить все объекты с ID = 2.
Я могу сделатьбинарный двоичный поиск и получение индекса 3, но как я могу получить (2 и 4), есть ли какой-нибудь эффективный алгоритм?
реальная проблема состоит в списках с примерно одним миллионом элементов.и лисп может помочь.

Answer 1

Вы можете создать карту, которая отображает идентификатор на коллекцию значений;

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

Это будет иметь эффективное время поиска O (1). Вы также можете выполнить бинарный поиск, но поиск будет менее эффективным.

Алгоритм двоичного поиска:

Сначала вы создаете отсортированный список (arraylist, связанный список и т. Д.). Это должно быть отсортировано по идентификатору. Затем вы делаете стандартный двоичный поиск, чтобы найти один элемент, который соответствует 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, который не совпадает. Это завершает восходящий цикл.