J'ai une liste triée de paires clé/valeur, et je veux trouver les valeurs adjacentes à une nouvelle clé

Question

J'ai une liste de paires clé/valeur (probablement utilisera une SortedList) et je ne vais pas ajouter de nouvelles valeurs. Au lieu de cela, j'utiliserai de nouvelles clés pour obtenir des valeurs limites. Par exemple, si je les clés/paires de valeurs suivantes:

(0,100) (6, 200), (9, 150), (15, 100), (20, 300) 

et j'ai la nouvelle clé de 7, je veux qu'il revienne 200 et 150, parce que 7 est compris entre 6 et 9.

Si Je donne 15 Je veux qu'il retourne 100 et 100 (parce que 15 est exactement 15). Je veux quelque chose comme une recherche binaire.

Merci

Answer 1

Vous pouvez le faire avec List<T>.BinarySearch:

var keys = new List<int>(sortedList.Keys); 
int index = keys.BinarySearch(target); 
int lower; 
int upper; 
if (index >= 0) { 
    lower = upper = index; 
} 
else { 
    index = ~index; 
    upper = index < keys.Count ? index : index - 1; 
    lower = index == 0 ? index : index - 1; 
} 

Console.WriteLine("{0} => {1}, {2}", 
    target, sortedList[keys[lower]], sortedList[keys[upper]]); 

Vous devez utiliser la valeur de retour de List<T>.BinarySearch pour obtenir les valeurs limites. De msdn, sa valeur de retour est la suivante:

« L'indice de base zéro de l'élément dans le tri List<T>, si le point est trouvé, sinon, une valeur négative qui est le complément au niveau du bit de l'indice de l'élément suivant qui est plus grand que l'élément ou, s'il n'y a pas d'élément plus grand, le complément au nombre de bits de Count. " En outre, pour les éléments inférieurs au premier ou au-delà du dernier, ce code «renvoie» le premier et le dernier deux fois, respectivement. Ce n'est peut-être pas ce que vous voulez, mais c'est à vous de définir vos conditions aux limites. Un autre est si la collection est vide, ce que je n'ai pas abordé.

Answer 2

Eh oui, vous voulez exactement recherche binaire - utiliser la méthode List<t>.BinarySearch, en particulier la surcharge en prenant un second argument IComparer (et mettre en œuvre cette interface avec une classe simple qui compare aux clés seulement).