Kann LINQ die binäre Suche verwenden, wenn die Sammlung geordnet ist?

Question

Kann ich irgendwie "anweisen" LINQ, binäre Suche zu verwenden, wenn die Sammlung, die ich versuche zu suchen, geordnet ist. Ich verwende eine ObservableCollection<T> die mit geordneten Daten gefüllt ist, und ich versuche, mit Enumerable.First(<Prädikat>) . In meinem Prädikat filtere ich nach dem Wert des Feldes, nach dem meine Sammlung sortiert ist.

Answer 1

Soweit ich weiß, ist das mit den eingebauten Methoden nicht möglich. Es wäre jedoch relativ einfach, eine Erweiterungsmethode zu schreiben, mit der man so etwas schreiben könnte:

var item = myCollection.BinarySearch(i => i.Id, 42);

(vorausgesetzt natürlich, dass Ihre Sammlung IList implementiert; es gibt keine Möglichkeit, eine binäre Suche durchzuführen, wenn Sie nicht zufällig auf die Elemente zugreifen können)

Hier ist ein Beispiel für eine Implementierung:

public static T BinarySearch<T, TKey>(this IList<T> list, Func<T, TKey> keySelector, TKey key)
        where TKey : IComparable<TKey>
{
    if (list.Count == 0)
        throw new InvalidOperationException("Item not found");

    int min = 0;
    int max = list.Count;
    while (min < max)
    {
        int mid = min + ((max - min) / 2);
        T midItem = list[mid];
        TKey midKey = keySelector(midItem);
        int comp = midKey.CompareTo(key);
        if (comp < 0)
        {
            min = mid + 1;
        }
        else if (comp > 0)
        {
            max = mid - 1;
        }
        else
        {
            return midItem;
        }
    }
    if (min == max &&
        min < list.Count &&
        keySelector(list[min]).CompareTo(key) == 0)
    {
        return list[min];
    }
    throw new InvalidOperationException("Item not found");
}

(nicht getestet... ein paar Anpassungen könnten notwendig sein) Jetzt getestet und behoben ;)

Die Tatsache, dass es eine InvalidOperationException mag seltsam erscheinen, aber das ist es, was Enumerable.First wenn es keinen passenden Artikel gibt.

Answer 2

Die akzeptierte Antwort ist sehr gut.

Ich benötige jedoch, dass die BinarySearch den Index des ersten Elements zurückgibt, das größer ist, da die List<T>.BinarySearch() tut.

Daher habe ich die Umsetzung mit Hilfe von ILSpy dann habe ich es so geändert, dass es einen Selektorparameter hat. Ich hoffe, es wird für jemanden so nützlich sein wie für mich:

public static class ListExtensions
{
    public static int BinarySearch<T, U>(this IList<T> tf, U target, Func<T, U> selector)
    {
        var lo = 0;
        var hi = (int)tf.Count - 1;
        var comp = Comparer<U>.Default;

        while (lo <= hi)
        {
            var median = lo + (hi - lo >> 1);
            var num = comp.Compare(selector(tf[median]), target);
            if (num == 0)
                return median;
            if (num < 0)
                lo = median + 1;
            else
                hi = median - 1;
        }

        return ~lo;
    }
}

Answer 3

Nun, Sie können Ihre eigene Erweiterungsmethode über ObservableCollection<T> - aber das wird dann verwendet für cualquier ObservableCollection<T> wo Ihre Erweiterungsmethode verfügbar ist, ohne zu wissen, ob sie sortiert ist oder nicht.

Man müsste auch im Prädikat angeben, was man finden will - was man besser mit einem Ausdrucksbaum machen sollte... aber das wäre mühsam zu parsen. Im Grunde genommen ist die Signatur von First ist nicht wirklich für eine binäre Suche geeignet.

Ich schlage vor, dass Sie nicht versuchen, die bestehende Signaturen, sondern schreiben eine neue, z. B.

public static TElement BinarySearch<TElement, TKey>
    (this IList<TElement> collection, Func<TElement, TItem> keySelector,
     TKey key)

(Ich werde es nicht sofort einführen, aber ich kann es später tun, wenn Sie wollen).

Wenn Sie eine Funktion bereitstellen, können Sie nach der Eigenschaft suchen, nach der die Sammlung sortiert ist, und nicht nach den Elementen selbst.

Answer 4

Enumerable.First(predicate) arbeitet an einem IEnumarable<T> die nur Aufzählungen unterstützt und daher keinen wahlfreien Zugriff auf die darin enthaltenen Elemente hat.

Außerdem enthält Ihr Prädikat willkürlichen Code, der letztendlich zu true oder false führt, und kann daher nicht angeben, ob das getestete Element zu niedrig oder zu hoch war. Diese Information wäre für eine binäre Suche erforderlich.

Enumerable.First(predicate) kann nur jedes Element der Reihe nach testen, wenn es die Aufzählung durchläuft.

Answer 5

Denken Sie daran, dass alle (? zumindest die meisten) der Erweiterungsmethoden, die von LINQ verwendet werden, auf IQueryable<T> oder IEnumerable<T> o IOrderedEnumerable<T> o IOrderedQueryable<T> .

Keine dieser Schnittstellen unterstützt den wahlfreien Zugriff und kann daher nicht für eine binäre Suche verwendet werden. Einer der Vorteile von LINQ ist, dass man mit großen Datensätzen arbeiten kann, ohne den gesamten Datensatz aus der Datenbank zurückgeben zu müssen. Natürlich kann man nicht binär suchen, wenn man noch nicht einmal alle Daten hat.

Aber wie andere schon sagten, gibt es überhaupt keinen Grund, warum man diese Erweiterungsmethode nicht auch für IList<T> oder andere Sammlungstypen, die den wahlfreien Zugriff unterstützen.