Routine that tests if a point is within a range

Question

Can anyone help me ?

for C#

I need to implement a routine that tests if a point is within a range ( array ), C#

in the figure below the ranges are [1-3],[6-9], [11-15]

i would like to use something like binarysearch, i used it but there is a flaw, because it can only test 2 ranges in this case ... if i have 2 ranges, the binarysearch works well because gives the 2 events in the IComparer for the 2 ranges. ([1-3],[6-9])

after i add 3 ranges the binarysearch only give me 2 ranges, [6-9], [11-15]

I'm using List<Tuple<int, int>> range, and IComparer<Tuple<int, int>>

something like that ---

class RangeComparerPoint : IComparer<Tuple<int, int>>
    {
        public int Compare(Tuple<int, int> f1, Tuple<int, int> f2)
        {
            //for the sake of clarity
            int boundary_1 = f1.Item1;
            int boundary_2 = f1.Item2;
            int pos = f2.Item1;
            int currPos = f2.Item2;

            //EndSection 
            if (pos > currPos)
            {
                if (pos >= boundary_1 && currPos < boundary_1)
                {
                    //in the range
                    return 0;
                }
            }
            else
            {
                if ( boundary_1 > currPos )
                {
                    return -1;
                }

                if (pos <= boundary_1)
                {
                    //in the range
                    return 0;
                }
            }
            return -1;
        }
    }

Answer 1

You need to be a bit more precise in framing the problem...

1. Ranges may not overlap (or implement logic to consolidate them)
2. Ranges are all closed intervals i.e. [1..3] means 1 <= x <= 3
   and you do not cater for (say) [1..4) meaning 1 <= x < 4
3. Integers only etc.

Going with these as assumptions and a bit of a kludge that requires you to search for Tuple<a,a> for the value a (see exception in Comp() method), here's an example of how to achieve what you're after...

using System;
using System.Collections;
using System.Collections.Generic;

namespace ConsoleApp2
{
  class Program
  {
    // x represents a point and y a range 
    // (params are swapped if necessary, i.e. if y is a point and x a range)
    // returns 0 if x falls within the range represented by y
    // returns -1 if x falls before y on the number line, +1 if it falls after y
    public static int Comp(Tuple<int, int> x, Tuple<int, int> y)
    {
      var fSwap = 1;
      if (x.Item1 != x.Item2) 
      {
        (x, y) = (y, x); // swap so that x is always the value being searched for
        fSwap = -1;
      }
      if (x.Item1 != x.Item2) // ***
        throw new Exception("The value being sought MUST be new Tuple(a,b) where a == b");
      return fSwap * (x.Item1 < y.Item1 ? -1 : x.Item1 > y.Item2 ? +1 : 0);
    }

    static void Main(string[] args)
    {
      // must be non-overlapping and increasing
      var ranges = new List<Tuple<int, int>>
      {
        new Tuple<int, int>(1, 3),
        new Tuple<int, int>(6, 9),
        new Tuple<int, int>(11,15)
      };

      for (int i = 0; i < 20; i++)
      {
        var foundIn = ranges.BinarySearch(new Tuple<int, int>(i, i), Comparer<Tuple<int, int>>.Create(Comp));
        if (foundIn < 0)
          Console.WriteLine($"{i} does not fall in any range");
        else
          Console.WriteLine($"{i} falls within [{ranges[foundIn].Item1},{ranges[foundIn].Item2}]");
      }
      Console.ReadKey();
    }
  }
}

Giving result...

0 does not fall in any range
1 falls within [1,3]
2 falls within [1,3]
3 falls within [1,3]
4 does not fall in any range
5 does not fall in any range
6 falls within [6,9]
7 falls within [6,9]
8 falls within [6,9]
9 falls within [6,9]
10 does not fall in any range
11 falls within [11,15]
12 falls within [11,15]
13 falls within [11,15]
14 falls within [11,15]
15 falls within [11,15]
16 does not fall in any range
17 does not fall in any range
18 does not fall in any range
19 does not fall in any range