У меня есть отсортированный список пар ключ / значение, и я хочу найти значения рядом с новым ключом

Question

У меня есть список пар ключ / значение (вероятно, я буду использовать SortedList), и я не буду добавлять новые значения.

Вместо этого я буду использовать новые ключи для получения ограничивающих значений. Например, если у меня есть следующие пары ключ / значение:

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

и у меня есть новый ключ 7, я хочу, чтобы он возвращал 200 и 150, потому что 7 между 6 и 9.

Если я даю 15, я хочу вернуть 100 и 100 (потому что 15 - это точно 15). Я хочу что-то вроде бинарного поиска.

Спасибо

Answer 1

Вы можете сделать это с помощью 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]]);

Вы должны использовать возвращаемое значение List<T>.BinarySearch, чтобы добраться до граничных значений. Начиная с msdn , его возвращаемое значение:

"Начинающийся с нуля индекс элемента в отсортированном List<T>, если элемент найден; в противном случае - отрицательное число, которое является побитовым дополнением индекса следующего элемента, который больше элемента или, если нет большего элемента, побитовое дополнение Count. "

Кроме того, для элементов, которые попадают ниже первого или после последнего, этот код «возвращает» первое и последнее дважды соответственно. Это может быть не то, что вы хотите, но это зависит от вас, чтобы определить свои граничные условия. Еще один случай, если коллекция пуста, к которой я не обращался.

Answer 2

Да, вы хотите точно бинарный поиск - используйте метод List<t>.BinarySearch, в частности перегрузку, принимающую второй аргумент IComparer (и реализуйте этот интерфейс с помощью простого класса aux, который просто сравнивает ключи) .