我需要编写线性插值代码，正在尝试找到在SortedList<K, V>的Key中搜索围绕目标Key的上下Key的最有效方法。
SortedList<int, double> xyTable = new SortedList<int, double>()
{
{1, 10}, {2, 20}, {3, 30}, {4,40}
};
double targetX = 3.5;
什么是最有效的搜索列表和确定3.5在3和4之间的方法？我有一个适用于整数的方法/技巧（将目标键暂时插入列表然后找到索引），但我想问问专家，以便我能够编写高质量的代码。
谢谢。
二分查找在列表中具有良好的性能。然而，SortedList上的Keys属性是IList类型，而BinarySearch是定义在List上的。幸运的是，您可以在这个相关问题中找到一个适用于IList的二分搜索实现：
-1。 - Evgeniy Berezovsky在我的情况下，源代码SortedList并没有太多的改变，因为它被用作查找表。所以，在这种情况下，将SortedList转换为List<T>是有意义的，可以进行一次转换。之后，使用内置的List<T>的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"
}
}
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个或更少元素时算法会做什么。
List<T>.BinarySearch()？ - svickList<T>的话，那就好办了，但是他只有IList<T>，所以你的解决方案实际上是一个很好的建议。 - svick来自MSDN，
SortedList对象的元素根据键按照创建SortedList时指定的特定IComparer实现或由键本身提供的IComparable实现进行排序。索引序列基于排序序列。当添加元素时，它会按照正确的排序顺序插入SortedList中，并相应地调整索引。当删除元素时，索引也会相应地调整。因此，随着从SortedList中添加或删除元素，特定键/值对的索引可能会改变。
*****该方法使用二进制搜索算法；因此，该方法是一个O(log n)操作，其中n为Count。*****
从.NET Framework 2.0开始，此方法使用集合对象的Equals和CompareTo方法在item上确定item是否存在。在早期版本的.NET Framework中，使用集合中的对象上的Equals和CompareTo方法来确定这一点。
换句话说，在SortedList中，IndexOfKey方法已经使用了二进制搜索算法，因此在您的情况下无需将其转换为List。
希望能有所帮助。