Can I use BinarySearch over a List of (start, end) Ranges to find a number covered by one Range

Question

I have a list of ranges, for example: (0, 1), (1, 4), (4, 8), (8, 14), (14, 20),
where Range is class with Start & End.

Can I apply a BinarySearch for searching a segment which contains value 10?
Any other way to implement this?

Answer 1

The general and most efficient way to query a collection of ranges, is implementing an Interval Tree. However, since your intervals never overlap, you can use a binary search approach.

So, here's what I would do.

Considering the Range class implemented as follows:

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

We create a comparer for the Range class that considers only the Start property (it's sufficient, since we assume there's no overlap) :

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

Then, here are the most important methods wrapped in an extensions class:

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

Usage example:

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

Note that Start edge is included while End edge is excluded (e.g. see the range20 example).

Credits to this SO post for the FindFirstIndexGreaterThanOrEqualTo method

Answer 2

You can use IComparer interface with BinarySearch

Regards

Answer 3

I've wrote my own function:

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