get a range of objects with binary search

Question

I have some data like this:

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

they are objects(not plain text).
and i want to get all objects with the ID = 2.
I can do a binary binary search and get the index 3,but how can i get (2 and 4) is there any efficient algorithm?
the real problem has lists with about one Million items.

any language except bf and lisp can help.

Answer 1

You can create a Map wich maps an id to a collection of values;

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

This will have an efficient lookup time of O(1). You can do the binary search as well, but lookups will be less efficient.

Binary search algorithm:

First you create a sorted list (arraylist, linkedlist, etc). It must be sorted on the id. Then you do a standard binary search to find one element that matches id. Then you traverse both upwards and downwards the list until element does not match id. This will find all objects with the given id.

Example list:

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

Binary search returns index 2. Now loop downwards will first find element 1: Id=2 which matches, then element 0: Id=1 which does not match and therefore terminates the downward loop. The upward loop first finds element 3: Id=3 which does not match. This terminates the upward loop.