二进制搜索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 <T>上执行二进制搜索？

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"
    }
}