Eine Bereichssuche in C# durchführen?

Question

Ich habe eine Liste von nicht-überlappenden Bereichen (Bereiche von Zahlen, z.B. 500-1000, 1001-1200 .. etc), gibt es eine elegante und schnelle Möglichkeit, Lookup zu tun, indem nur eine Zahl übergeben? Ich könnte List.BinarySearch() oder Array.BinarySearch() verwenden, aber ich muss den Typ des Bereichsobjekts übergeben (Array.BinarySearch(T[], T)), ich kann ein Dummy-Bereichsobjekt übergeben und die Aufgabe erledigen (nur den Vergleich mit dem Bereichsanfang durchführen), aber ich frage mich, ob dies auf sauberere Weise geschehen kann, indem ich nur eine ganze Zahl übergebe und das Bereichsobjekt erhalte.

Answer 1

Drei Optionen:

• Erstellen Sie einen Dummy-Bereich und schlucken Sie ihn. Urgh.
• Erstellen Sie eine binäre Suche nur für diesen Fall. Gar nicht so schlecht.
• Verallgemeinern Sie die binäre Suche für eine beliebige IList und einen TValue, gegeben einen IRangeComparer. Ich bin nicht wild auf den Namen "TRange" hier - wir sind nicht unbedingt über Bereiche sprechen, sondern nur die Suche nach der richtigen Stelle auf der Grundlage eines Vergleichs zwischen zwei verschiedenen Typen.

Die dritte Option würde lauten etwas mögen:

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;
}

Ich bitte um Entschuldigung, wenn ich irgendwelche Fehler gemacht habe. Ich habe es überhaupt nicht getestet, aber es kompiliert zumindest :)

Answer 2

Wenn Sie .Net 3.5 oder höher haben, versuchen Sie

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

Answer 3

Wenn Sie viele Bereiche haben und sich wirklich Sorgen um die Leistung machen, können Sie eine AVL Baumart bestehend aus den Paaren des Bereichs(min,max), aber sortiert nach dem untersten Teil des Bereichs.

Wenn Sie jedoch nicht viele Bereiche haben, in die Sie die Dinge einsortieren können, ist dies eine Menge Arbeit für praktisch keinen Gewinn.