I want to have data structure with (start,end) as key and then be able to search integer in whole data structure and get corresponding value

Question

I'd like to have a

data structure with <Key, Value> where
  Key = (start, end), 
  Value = string

After which I should be able to search an integer optimally in the data structure and get corresponding value.

Example:

var lookup = new Something<(int, int), string>()
{
  {(1,100),"In 100s"},
  {(101,200),"In 100-200"},
}

var value1 = lookup[10]; //value1 = "In 100s"
var value2 = lookup[110]; //value2 = "In 100-200"

Could anyone suggest?

Answer 1

If you want to be able to use something like lookup[10] as you mentioned, you can create your own class that implements some sort of key/value data type. Which underlying data type you ultimately decide to use really depends on what your data looks like.

Here's a simple example of doing this while implementing a Dictionary<>:

public class RangeLookup : Dictionary<(int Min, int Max), string>
{
    public string this[int index] => this.Single(x => x.Key.Min <= index && index <= x.Key.Max).Value;
}

This allows you to define a custom indexer on top of the dictionary to encapsulate your range lookup. A usage of this class would look like:

var lookup = new RangeLookup
{
    { (1, 100), "In 100s" },
    { (101, 200), "In 101-200s" },
};

Console.WriteLine($"50: {lookup[50]}");

Which produces output as:

---

In terms of performance with this approach, the following is an example of some tests (using Win10 with an Intel i7-4770 CPU) retrieving a value from a dictionary with 10,000,000 records:

var lookup = new RangeLookup();

for (var i = 1; i <= 10000000; i++)
{
    var max = i * 100;
    var min = max - 99;
    lookup.Add((min, max), $"In {min}-{max}s");
}

var stopwatch = new Stopwatch();

stopwatch.Start();
Console.WriteLine($"50: {lookup[50]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

stopwatch.Restart();
Console.WriteLine($"5,000: {lookup[5000]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

stopwatch.Restart();
Console.WriteLine($"1,000,000,000: {lookup[1000000000]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

Which gives the following results:

So unless you plan on working with more than tens of millions of records inside of this data set, an approach like this should be satisfactory in terms of performance.

Answer 2

You basically have a Dictionary<> structure here, for example:

var lookup = new Dictionary<(int, int), string>()
{
  {(1,100),"In 100s"},
  {(101,200),"In 100-200"},
};

You can use some basic Linq queries to search that container, for example:

var searchValue = 10;
var value1 = lookup.First(l => l.Key.Item1 <= searchValue && l.Key.Item2 >= searchValue);

searchValue = 110;
var value2 = lookup.First(l => l.Key.Item1 <= searchValue && l.Key.Item2 >= searchValue);

But as Lee suggested in the comments, you might get better performance using a SortedDictionary, your mileage may vary, which means you need to test the performance of both.