Как упоминалось ранее, если набор диапазонов большой и не перекрывается, лучше всего выполнить бинарный поиск. Один из способов сделать это - использовать SortedDictionary, который реализует красно-черное дерево, чтобы дать время поиска O (log (n)). Мы можем использовать диапазоны в качестве ключей и выполнить поиск по словарю, преобразовав одно значение, которое мы хотим сопоставить, в диапазон из одной точки. Если мы реализуем метод CompareTo, чтобы перекрывающиеся диапазоны считались равными или совпадающими, поиск по словарю найдет подходящий диапазон для использования.
public struct Range : IComparable<Range>
{
public int From;
public int To;
public Range(int point)
{
From = point;
To = point;
}
public Range(int from, int to)
{
From = from;
To = to;
}
public int CompareTo(Range other)
{
// If the ranges are overlapping, they are considered equal/matching
if (From <= other.To && To >= other.From)
{
return 0;
}
// Since the ranges are not overlapping, we can compare either end
return From.CompareTo(other.From);
}
}
public class RangeDictionary
{
private static SortedDictionary<Range, string> _ranges = new SortedDictionary<Range, string>();
public RangeDictionary()
{
_ranges.Add(new Range(1, 1000), "Alice");
_ranges.Add(new Range(1001, 2000), "Bob");
_ranges.Add(new Range(2001, 3000), "Carol");
}
public string Lookup(int key)
{
/* We convert the value we want to lookup into a range,
* so it can be compared with the other ranges */
var keyAsRange = new Range(key);
string value;
if (_ranges.TryGetValue(keyAsRange, out value))
{
return value;
}
return null;
}
}
В качестве примера запускаем следующий код
var ranges = new RangeDictionary();
var value = ranges.Lookup(1356);
value в этом случае будет содержать строку "Bob", поскольку 1356 соответствует диапазону 1001-2000.
В вашем случае, если вы заинтересованы в извлечении самого диапазона, вы можете использовать диапазон как ключ и значение в словаре. Код примера может быть легко расширен для хранения общих значений.
Как примечание, этот трюк также может быть выполнен с использованием SortedList практически с тем же кодом, который использует меньше памяти (массив вместо дерева), но имеет более медленное время вставки / удаления для несортированных данных. Они оба используют компаратор по умолчанию для типа ключа (или указанного) для сравнения значений. Обычный C # Dictionary, с другой стороны, использует GetHashCode и Equals для сравнения значений.