在C#中从已排序元组列表查找下一个最近值的方案问询

一、基于现有List的高效查找实现 #

由于你的List已经按column1升序排列，二分查找是最高效的方式（时间复杂度O(log n)），无需遍历整个列表。以下是实现代码：

public (double column1, double column2)? FindFirstGreaterThan(double target)
{
    int left = 0;
    int right = myList.Count - 1;
    int matchIndex = -1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2; // 避免整数溢出
        var currentTuple = myList[mid];
        
        if (currentTuple.column1 > target)
        {
            matchIndex = mid;
            right = mid - 1; // 继续向左寻找更小的符合条件的索引
        }
        else
        {
            left = mid + 1; // 当前元素不满足，向右查找
        }
    }

    return matchIndex != -1 ? myList[matchIndex] : null;
}

逻辑说明： #

• 当中间元素的column1大于目标值时，记录当前索引并继续向左搜索，确保找到最小的符合条件的索引（即第一列大于目标值的最小元组）。
• 如果所有元素的column1都小于等于目标值，返回null。

二、适配动态添加元素的数据结构推荐 #

如果未来需要频繁添加元素且保持排序，List的插入操作（中间位置）时间复杂度为O(n)（需要移动后续元素），推荐以下两种更高效的结构：

1. SortedDictionary<double, double>（适用于column1唯一的场景） #

基于红黑树实现，插入、删除、查找的时间复杂度均为O(log n)，自带按键（column1）升序排序的特性。

示例代码：

// 初始化
private SortedDictionary<double, double> mySortedDict = new SortedDictionary<double, double>
{
    {6,80}, {8,107}, {10,134}, {12,160}, {16,214}, {20,267}, {25,334}, {32,427}, {40,534}
};

// 查找方法
public (double column1, double column2)? FindFirstGreaterThanDict(double target)
{
    // 获取所有大于target的键的视图
    var keyView = mySortedDict.Keys.GetViewBetween(target, double.MaxValue);
    if (keyView.Any())
    {
        var firstKey = keyView.First();
        return (firstKey, mySortedDict[firstKey]);
    }
    return null;
}

2. SortedSet<(double column1, double column2)>（适用于column1可能重复的场景） #

同样基于红黑树实现，支持重复的column1值，需要自定义比较器确保按column1排序。

示例代码：

// 自定义比较器，按column1排序
public class TupleColumn1Comparer : IComparer<(double column1, double column2)>
{
    public int Compare((double column1, double column2) x, (double column1, double column2) y)
    {
        return x.column1.CompareTo(y.column1);
    }
}

// 初始化
private SortedSet<(double column1, double column2)> mySortedSet = new SortedSet<(double column1, double column2)>(new TupleColumn1Comparer())
{
    (6,80), (8,107), (10,134), (12,160), (16,214), (20,267), (25,334), (32,427), (40,534)
};

// 查找方法
public (double column1, double column2)? FindFirstGreaterThanSet(double target)
{
    // 构造最小的匹配元组，确保column1 > target
    var lowerBound = (target + double.Epsilon, double.MinValue);
    var upperBound = (double.MaxValue, double.MaxValue);
    
    var match = mySortedSet.GetViewBetween(lowerBound, upperBound).FirstOrDefault();
    return match.column1 > target ? match : null;
}

选择建议 #

• 如果column1不会重复，优先使用SortedDictionary，代码更简洁，操作效率稳定。
• 如果column1可能重复，使用SortedSet配合自定义比较器。
• 如果添加元素的频率极低，现有List加二分查找的方案完全够用，无需更换结构。

内容的提问来源于stack exchange，提问作者Lucas Gamaleri