Ho un elenco ordinato di coppie chiave/valore e voglio trovare i valori adiacenti a una nuova chiave

Question

Ho un elenco di coppie chiave/valori (probabilmente utilizzerò una EordindList) e non aggiungerò nuovi valori.

Invece userò nuove chiavi per ottenere valori di delimitazione. Ad esempio, se ho le seguenti coppie chiave/valore:

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

E ho la nuova chiave di 7, voglio che restituisca 200 e 150, perché 7 è tra 6 e 9.

Se do 15 voglio che restituisca 100 e 100 (perché 15 è esattamente 15). Voglio qualcosa come una ricerca binaria.

Grazie

Answer 1

Puoi farlo con 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]]);

Devi usare il valore di ritorno di List<T>.BinarySearch Per raggiungere i valori di confine. Da msdn, il suo valore di ritorno è:

"L'indice a base zero dell'articolo nell'ordinato List<T>, se si trova l'oggetto; Altrimenti, un numero negativo che è il complemento bitwise dell'indice dell'elemento successivo che è più grande dell'articolo o, se non esiste un elemento più grande, il complemento bitwise del conteggio. "

Inoltre, per elementi che scendono al di sotto della prima o oltre l'ultimo, questo codice "restituisce" il primo e l'ultimo due volte, rispettivamente. Questo potrebbe non essere quello che vuoi, ma dipende da te definire le condizioni al contorno. Un altro è se la raccolta è vuota, che non ho affrontato.

Answer 2

Sì, vuoi Esattamente Ricerca binaria: usa il List<t>.BinarySearch Metodo, in particolare il sovraccarico che prende un file IComparer Secondo argomento (e implementa quell'interfaccia con una semplice classe AUX che confronta solo le chiavi).