我可以在(开始，结束)范围列表上使用二进制搜索来查找一个范围所涵盖的数字吗?

范围集合的通用和最有效的方法是实现间隔树。但是，由于间隔永远不会重叠，因此可以使用二叉搜索方法。

所以，这就是我要做的。

考虑实现如下的Range类：

class Range
{
    public int Start { get; private set; }
    public int End { get; private set; }
    public Range(int start, int end)
    {
        this.Start = start;
        this.End = end;
    }
}

我们为仅考虑Start属性的 Range 类创建一个比较器（这就足够了，因为我们假设没有重叠）：

class StartOnlyRangeComparer : IComparer<Range>
{
    public int Compare(Range x, Range y)
    {
        return x.Start.CompareTo(y.Start);
    }
}

然后，以下是包装在扩展类中的最重要的方法：

static class Extensions
{
    /// <summary>
    /// N.B. ranges must be sorted by ascending Start, must contain 
    ///      non overlapping ranges and ranges with Start=End are not allowed.
    /// </summary>
    /// <param name="ranges"></param>
    /// <param name="point"></param>
    /// <returns></returns>
    public static Range FindRangeContainingPoint(
        this IList<Range> ranges, int point)
    {
        if (ranges.Count == 0)
            return null;
        var index = ranges.FindFirstIndexGreaterThanOrEqualTo(
                    new Range(point, point + 1),
                    new StartOnlyRangeComparer());
        if (index < 0)
            return null; // no existing range contains the point, 
                         // if we wanted to insert a Range(point, point+1) 
                         // would be before the first element 
        if (index >= ranges.Count)
        {
            var lastElement = ranges[ranges.Count - 1];
            if (lastElement.ContainsPoint(point))
                return lastElement;
            else
                return null; // no existing range contains the point,  
                             // if we wanted to insert a Range(point, point+1)
                             // would be after the last element
        }
        if (ranges[index].ContainsPoint(point))
            return ranges[index];
        else if (index > 0 && ranges[index - 1].ContainsPoint(point))
            return ranges[index - 1];
        else
            return null; // no existing range contains the point,  
                         // if we wanted to insert a Range(point, point+1)
                         // would be at index - 1
    }
    /// <summary>
    /// Lower Bound function on sorted list (see credits)
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="sortedCollection"></param>
    /// <param name="key"></param>
    /// <param name="comparer"></param>
    /// <returns></returns>
    public static int FindFirstIndexGreaterThanOrEqualTo<T>(
        this IList<T> sortedCollection,
        T key,
        IComparer<T> comparer)
    {
        int begin = 0;
        int end = sortedCollection.Count;
        while (end > begin)
        {
            int index = begin + ((end - begin) / 2);
            T el = sortedCollection[index];
            if (comparer.Compare(el, key) >= 0)
                end = index;
            else
                begin = index + 1;
        }
        return end;
    }
    /// <summary>
    /// Check if point is included in [Start, End)
    /// </summary>
    /// <param name="point"></param>
    /// <returns></returns>
    public static bool ContainsPoint(this Range range, int point)
    {
        return range.Start <= point && range.End > point;
    }
}

使用示例：

class Program
{
    static void Main(string[] args)
    {
        var list = new List<Range>()
        {
            new Range(0, 1), 
            new Range(1, 4), 
            new Range(4, 8), 
            new Range(8, 14), 
            new Range(14, 20),
            new Range(22, 24),
        };
        // yes I know in this case they're already sorted...
        // but I want to stress the fact that you must sort the list
        list.Sort(new StartOnlyRangeComparer()); 
        var range10 = list.FindRangeContainingPoint(10); // returns (8,14)
        var range21 = list.FindRangeContainingPoint(21); // returns null
        var range20 = list.FindRangeContainingPoint(20); // returns null
        var range14 = list.FindRangeContainingPoint(14); // return (14,20)
   }
}

请注意，Start边被排除End而边被排除（例如，请参阅range20示例）。

此SO帖子的FindFirstIndexGreaterThanOrEqualTo方法

您可以将 IComparer 接口与 BinarySearch 一起使用

问候

我编写了自己的函数：

public Range BinarySearch(double position)
{
    Range part = null;
    int from = 0;
    int to = Count - 1;
    while (from < to)
    {
        int middle = (from + to) / 2;
        part = this[middle];
        switch (part.CompareTo(position))
        {
            case 1:
                from = Math.Min(middle + 1, to);
                break;
            case -1:
                to = Math.Max(middle - 1, from);
                break;
            case 0:
                from = to = middle;
                break;
        }
    }
    return this[to];
}