Делаете поиск диапазона в C #?

Question

У меня есть список непересекающихся диапазонов (диапазоны чисел, например, 500-1000, 1001-1200 и т. Д.), Есть ли элегантный и быстрый способ поиска, только передавая число? Я мог бы использовать List.BinarySearch () или Array.BinarySearch (), но мне нужно передать тип объекта диапазона (Array.BinarySearch (T [], T)), я могу передать фиктивный объект диапазона и выполнить работу (только сравнение с началом диапазона), но мне было интересно, если это можно сделать более чистым способом, только передавая целое число и получая объект диапазона, есть ли способ достичь этого?

Answer 1

Три варианта:

• Создайте фиктивный Range и поглотите его. Urgh.
• Ручной бинарный поиск только для этого случая. Не так уж плохо.
• Обобщение бинарного поиска для любого IList и TValue, заданного IRangeComparer. Я не в восторге от названия «TRange» здесь - мы не обязательно говорим о диапазонах, но просто находим правильное место, основываясь на сравнении двух разных типов.

Третий вариант: что-то , например:

public interface IRangeComparer<TRange, TValue>
{
    /// <summary>
    /// Returns 0 if value is in the specified range;
    /// less than 0 if value is above the range;
    /// greater than 0 if value is below the range.
    /// </summary>
    int Compare(TRange range, TValue value);
}


/// <summary>
/// See contract for Array.BinarySearch
/// </summary>
public static int BinarySearch<TRange, TValue>(IList<TRange> ranges,
                                               TValue value,
                                               IRangeComparer<TRange, TValue> comparer)
{
    int min = 0;
    int max = ranges.Count-1;

    while (min <= max)
    {
        int mid = (min + max) / 2;
        int comparison = comparer.Compare(ranges[mid], value);
        if (comparison == 0)
        {
            return mid;
        }
        if (comparison < 0)
        {
            min = mid+1;
        }
        else if (comparison > 0)
        {
            max = mid-1;
        }
    }
    return ~min;
}

Извините, если у меня возникли какие-то ошибки. Я вообще не проверял, но он по крайней мере компилируется:)

Answer 2

Если у вас есть .Net 3.5 или выше, попробуйте

foundRange = yourList.Where(range =› range.BottomNumber ‹= searchInt && range.TopNumber ›= searchInt).FirstOrDefault();

Answer 3

Если у вас много диапазонов и вы действительно беспокоитесь о производительности, вы можете создать дерево типа AVL , состоящее из пар диапазона (мин, макс), но отсортированных по самая низкая часть диапазона.

Однако, если у вас нет большого количества диапазонов для сортировки, это большая работа практически без выгоды.