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

Ответ 1

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

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

Ответ 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"
    }
}

Ответ 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 фактически использует алгоритм binarySearch, поэтому нет необходимости преобразовывать форму SortedList в List в вашем случае.

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

Ответ 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);
}

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