Двоичный поиск по ключам SortedList <K, V>

Question

Мне нужно написать некоторый код для линейной интерполяции, и я пытаюсь найти наиболее эффективный способ поиска ключей SortedList<K, V> для верхних и нижних клавиш, которые окружают мой целевой ключ.

SortedList<int, double> xyTable = new SortedList<int, double>()
{
    {1, 10}, {2, 20}, {3, 30}, {4,40}
};

double targetX = 3.5;

Каков наиболее эффективный способ поиска в списке и определения 3,5 между 3 и 4? У меня есть метод / чит, который работает для целых чисел (временно вставьте целевой ключ в список, затем найдите индекс), но я решил спросить у профи, чтобы я мог создать качественный код.

Спасибо.

Answer 1

Бинарный поиск дает вам достойную производительность в списке. Однако свойство Keys для SortedList имеет тип IList, тогда как BinarySearch определено для List. К счастью, вы можете найти реализацию бинарного поиска для IList в этом связанном вопросе:

Как выполнить бинарный поиск по IList ?

Answer 2

В моем случае источник SortedList не сильно меняется, так как он используется в качестве справочной таблицы.Так что в этом случае имеет смысл преобразовать SortedList в List<T> один раз.После этого довольно просто использовать встроенный метод BinarySearch List<T> ...

double targetX = 3.5;

// Assume keys are doubles, may need to convert to doubles if required here.
// The below line should only be performed sparingly as it is an O(n) operation.
// In my case I only do this once, as the list is unchanging.
List<double> keys = xyTable.Keys.ToList();

int ipos = keys.BinarySearch(targetX);

if (ipos >= 0)
{
    // exact target found at position "ipos"
}
else
{
    // Exact key not found: BinarySearch returns negative when the 
    // exact target is not found, which is the bitwise complement 
    // of the next index in the list larger than the target.
    ipos = ~ipos;
    if (ipos >= 0 && ipos < keys.Count)
    {
        if (ipos > 0)
        {
            // target is between positions "ipos-1" and "ipos"
        }
        else
        {
            // target is below position "ipos"
        }
    }
    else
    {
        // target is above position "ipos"
    }
}

Answer 3

Из MSDN,

Элементы объекта SortedList сортируются по ключам либо согласно конкретной реализации IComparer, указанной при создании SortedList, либо согласно реализации IComparable, предоставляемой самими ключами.Последовательность индекса основана на последовательности сортировки.Когда элемент добавляется, он вставляется в SortedList в правильном порядке сортировки, и индексирование корректируется соответствующим образом.Когда элемент удаляется, индексирование также корректируется соответствующим образом.Поэтому индекс конкретной пары ключ / значение может измениться при добавлении или удалении элементов из SortedList.

***** Этот метод использует алгоритм двоичного поиска;поэтому этот метод является операцией O (log n), где n равно Count. *****

Начиная с .NET Framework 2.0, этот метод использует методы Equals и CompareTo объектов коллекции для элемента.определить, существует ли элемент.В более ранних версиях .NET Framework это определение делалось с использованием методов Equals и CompareTo параметра item для объектов в коллекции.

Другими словами, метод IndexOfKey в SortedList фактически используетАлгоритм двоичного поиска уже, поэтому нет необходимости преобразовывать форму SortedList в список в вашем случае.

Надеюсь, это поможет ..

Answer 4

public class Bounds
{
    int lower;
    int upper;

    public Bounds(int lower, int upper)
    {
       this.lower = lower;
       this.upper = upper;
    }
}

public Bounds BinarySearch(List<int> keys, double target)
{
    // lower boundary case returns the smallest key as the lower and upper bounds
    if (target < keys[0])
        return new Bounds(0, 0);

    else if (target < keys[1])
        return new Bounds(0, 1);

    // upper boundary case returns the largest key as the lower and upper bounds
    else if (target > keys[keys.Length - 1])
        return new Bounds(keys.Length - 1, keys.Length - 1);

    else if (target > keys[keys.Length - 2])
        return new Bounds(keys.Length - 2, keys.Length - 1);

    else
        return BinarySearch(keys, target, 0, keys.Length - 1);

}

// 'keys' is a List storing all of the keys from your SortedList.
public Bounds BinarySearch(List<int> keys, double target, int lower, int upper)
{
    int middle = (upper + lower)/2;

    // target is equal to one of the keys
    if (keys[middle] == target)
        return new Bounds(middle - 1, middle + 1);

    else if (keys[middle] < target && keys[middle + 1] > target)
        return new Bounds(middle, middle + 1);

    else if (keys[middle] > target && keys[middle - 1] < target)
        return new Bounds(middle - 1, middle);

    if (list[middle] < target)
         return BinarySearch(list, target, lower, upper/2 - 1);

    if (list[middle] > target)
         return BinarySearch(list, target, upper/2 + 1, upper);
}

Это может сработать .. Я не проверял это.Если нет, надеюсь, он достаточно близко, чтобы вы могли использовать его с небольшими изменениями.Это странная проблема, поэтому я обработал все граничные случаи, поэтому мне не приходилось думать о том, что будет делать алгоритм, когда диапазон уменьшится до 2 элементов или менее.