对 SortedList的键进行二分查找

Question

我需要编写一些用于线性插值的代码，并且我正在尝试找出最有效的方法来搜索 SortedList 的键以查找目标键周围的上下键。

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

二分搜索可以在列表上提供不错的性能。但是，SortedList 上的 Keys 属性是 IList 类型，而 BinarySearch 是在 List 上定义的。幸运的是，您可以在此相关问题中找到 IList 的二分搜索实现：

如何对 IList执行二分查找？

Answer 2

就我而言，源 SortedList 变化不大，因为它被用作查找表。因此，在这种情况下，将 SortedList 转换为 List 一次是有意义的。之后就很容易使用 List 内置的 BinarySearch 方法了...

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

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 个元素或更少时算法会做什么。

Answer 4

根据 MSDN，

SortedList 对象的元素根据创建 SortedList 时指定的特定 IComparer 实现或根据键本身提供的 IComparable 实现按键排序。
索引顺序基于排序顺序。添加元素时，它会以正确的排序顺序插入到 SortedList 中，并且索引也会相应调整。当删除元素时，索引也会相应调整。因此，当在 SortedList 中添加或删除元素时，特定键/值对的索引可能会发生变化。

*****该方法使用二分查找算法；因此，此方法是一个 O(log n) 操作，其中 n 是 Count。*****

从 .NET Framework 2.0 开始，此方法使用集合对象的 item 的 Equals 和 CompareTo 方法来确定 item 是否存在。在 .NET Framework 的早期版本中，此确定是通过对集合中的对象使用 item 参数的 Equals 和 CompareTo 方法来做出的。

换句话说，SortedList 中的 IndexOfKey 方法实际上已经使用了二元搜索算法，因此在您的情况下不需要将 SortedList 转换为 List。

希望有帮助..