c# - 在 C# 中进行范围查找？

Question

我有一个非重叠范​​围列表(数字范围，例如 500-1000、1001-1200 .. 等)，是否有一种优雅而快速的方法来仅传递一个数字来进行查找？我可以使用 List.BinarySearch() 或 Array.BinarySearch() 但我必须传递范围对象的类型 (Array.BinarySearch(T[], T))，我可以传递一个虚拟范围对象并完成工作(仅与范围开始进行比较)但我想知道是否可以通过仅传递整数并获取范围对象以更简洁的方式完成此操作，有没有办法实现此目的？

Answer 1

三个选项:

• 创建一个虚拟范围并将其吸收。呃。
• 专门为这种情况手工制作二分搜索。还不错。
• 在给定 IRangeComparer 的情况下，对任何 IList 和 TValue 进行二进制搜索。我对这里的“TRange”这个名称并不狂热 - 我们不一定在谈论范围，而只是根据两种不同类型之间的比较找到合适的位置。

第三个选项将是某事，例如:

public interface IRangeComparer<TRange, TValue>
{
    /// <summary>
    /// Returns 0 if value is in the specified range;
    /// less than 0 if value is above the range;
    /// greater than 0 if value is below the range.
    /// </summary>
    int Compare(TRange range, TValue value);
}


/// <summary>
/// See contract for Array.BinarySearch
/// </summary>
public static int BinarySearch<TRange, TValue>(IList<TRange> ranges,
                                               TValue value,
                                               IRangeComparer<TRange, TValue> comparer)
{
    int min = 0;
    int max = ranges.Count-1;

    while (min <= max)
    {
        int mid = (min + max) / 2;
        int comparison = comparer.Compare(ranges[mid], value);
        if (comparison == 0)
        {
            return mid;
        }
        if (comparison < 0)
        {
            min = mid+1;
        }
        else if (comparison > 0)
        {
            max = mid-1;
        }
    }
    return ~min;
}

如果我有任何不对一的错误，我深表歉意。我根本没有测试过它，但它至少可以编译 :)