Ohne Verwendung von Erweiterungsmethoden (LINQ). Ich bin leider auf .NET 2.0 beschränkt. (Ja, es ist zum Kotzen)Generic SortedList, Wie finde ich den Index des ersten Elements, das größer als der Suchschlüssel ist?
Auf der Suche nach etwas in der Nähe von O (log (n)).
Danke für Ihre Hilfe.
Um den ersten Schlüssel zu finden, der größer als ein Schlüssel ist, können Sie die Schlüsselliste SortedList<T>.Keys verwenden und Binary Search oder Interpolation Search auf den Schlüsseln ausführen. Dies ergibt O(log(n)) (MSDN besagt, dass ein Schlüssel nachschlagen ist O(1)).
Ja! Erster Schlüssel, der größer als der Suchschlüssel oder sogar erster Schlüssel ist, der kleiner als der Suchschlüssel ist. Danke für deine Zeit. – Newbie
Binär suchen Sie nach einem O (n log n) Lookup.
Siehe http://en.wikipedia.org/wiki/Binary_search für die Erklärung, obwohl ich mir nicht vorstellen kann, dass Sie es brauchen. – Brian
Die binäre Suche ist O (log (n)), wenn der Elementzugriff O (1) ist. –
suchen, wo die Dinge in oder O sind (log n) binäre Suche
Suche nach, wo die Dinge sind O (n) linear nicht in Ordnung. Kann es nicht besser machen, wenn die Dinge nicht in Ordnung sind.
Die Idee, die Werte der Reihenfolge nach zu ordnen, nimmt O (n * log (n)) an, es sei denn, Sie werden dies immer wieder machen und das Ergebnis zwischenspeichern, warum? benutzen Sie einfach Ihre lineare Suche.
(beachten Sie, Sie waren daran interessiert, den Wert nicht den Schlüssel zu suchen)
Ich rieche Hausaufgaben. – dss539
dss539: Lesen Sie die FAQ zu StackOverflow. Sie stellen ziemlich klar fest, dass Hausaufgabenfragen nicht ignoriert werden sollten. – TheTXI
Ich wünschte, es wäre Homerwork, aber nein, echte Arbeit hier. – Newbie