C #: Хранение набора неперекрывающихся диапазонов и нахождение, присутствует ли значение строго в любом из диапазонов

Question

У меня есть набор диапазонов:

Диапазон1 ---- (0-10)

Диапазон 2 ---- (15-25)

Range3 ---- (100-1000) и аналогично. Я хотел бы хранить только границы, так как при хранении больших диапазонов это будет эффективно.

Теперь мне нужно найти число, скажем, 14. В этом случае 14 не присутствует ни в одном из диапазонов, тогда как (скажем, число) 16 присутствует в одном из диапазонов.

Мне нужна функция

bool search (диапазоны, searchvalue) { если поисковые значения присутствуют в любом из диапазонов вернуть истину; еще вернуть ложь; } Как лучше всего это сделать? Это строго не совпадает, и важным критерием является то, что поиск должен быть наиболее эффективным.

есть аналогичный вопрос, который я задал, учитывая C ++, где мы можем использовать карту или вектор. Но как это лучше всего сделать на C #?

Answer 1

Вы можете определить диапазон классов и выполнить бинарный поиск по нему: лучше сохранять список отсортированным при запуске или с помощью sortedlist

    public class Range : IComparable
    {
        public int start;
        public int end;
        public int CompareTo(object obj)
        {
            var result = obj as Range;
            if (result == null)
                return 1;
            if (start > result.start)
                return 1;
            if (result.start >= start && result.end <= end)
                return 0;
            return -1;
        }
    }
    public void findItemInRange(List<Range> ranges, int item)
    {
        // ranges.Sort(); I'll assume list is sorted
        int positionOfItem = ranges.
                            BinarySearch(new Range { start = item, end = item });
    }