c# - (開始、終了) 範囲のリストに対して BinarySearch を使用して、1 つの範囲に含まれる数値を検索できますか?

Question

たとえば、(0, 1)、(1, 4)、(4, 8)、(8, 14)、(14, 20) の範囲のリストがあります。
ここで、Range は Start & End のクラスです。

値 10 を含むセグメントを検索するために BinarySearch を適用できますか?
これを実装する他の方法はありますか？

Answer 1

範囲のコレクションを照会する一般的で最も効率的な方法は、Interval Treeを実装することです。ただし、間隔が重複することはないため、二分探索アプローチを使用できます。

だから、これが私がすることです。

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

Rangeプロパティのみを考慮するクラスの比較子を作成しStartます (重複はないと仮定しているため、これで十分です)。

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れている間、エッジが含まれていることに注意してください(例を参照してください)。Endrange20

メソッドのこの SO 投稿へのクレジットFindFirstIndexGreaterThanOrEqualTo

Answer 2

BinarySearchで IComparer インターフェイスを使用できます

よろしく