obtenir une gamme d'objets avec la recherche binaire

Question

J'ai quelques données comme ceci:

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

Ce sont des objets (pas le texte brut).
et je veux obtenir tous les objets avec l'ID = 2.
Je peux faire une recherche binaire binaire et obtenir l'index 3, mais comment puis-je obtenir (2 et 4) y at-il un algorithme efficace?
le vrai problème a des listes avec environ un million d'articles.

toute langue sauf bf et Lisp peut aider.

Answer 1

Vous pouvez créer une carte mappant un ID à une collection de valeurs;

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

Cela aura un temps de recherche efficace de O (1). Vous pouvez également effectuer la recherche binaire, mais les recherches seront moins efficaces.

algorithme de recherche binaire:

D'abord, vous créez une liste triée (arraylist, chaînée, etc.). Il doit être trié sur l'identifiant. Ensuite, vous effectuez une recherche binaire standard pour trouver un élément qui correspond à l'ID. Ensuite, vous traversez la liste vers le haut et vers le bas jusqu'à ce que l'élément ne corresponde pas à l'identifiant. Cela trouvera tous les objets avec l'ID donné.

Exemple Liste:

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 

recherche binaire retourne l'index 2. Maintenant boucle vers le bas d'abord trouver l'élément 1: Id = 2 qui correspond, alors élément 0: Id = 1 qui ne correspond pas à et se termine donc la boucle descendante. La boucle ascendante trouve d'abord l'élément 3: Id = 3 qui ne correspond pas. Ceci termine la boucle ascendante.