Общий SortedList, Как найти индекс первого элемента, который больше, чем ключ поиска?

Question

Без использования методов расширений (LINQ). К сожалению, я ограничен .NET 2.0. (Да, это отстой)

Ищем что-то близкое к O (log (n)).

Спасибо за вашу помощь.

Answer 1

Чтобы найти первый ключ, который больше данного ключа, вы можете использовать список ключей SortedList<T>.Keys и выполнить Бинарный поиск или Интерполяционный поиск по ключам. Это даст O(log(n)) ( MSDN утверждает, что поиск ключа - O(1)).

Answer 2

Двоичный поиск для поиска O (n log n).

Answer 3

поиск, где все в порядке o (log n) бинарный поиск

поиск, где вещи не в порядке O (n) линейный. Не может быть лучше, если все не в порядке.

Идея упорядочения значений по порядку требует O (n * log (n)), если вы не собираетесь делать это снова и снова и кэшировать результат, зачем беспокоиться? просто используйте свой линейный поиск.

(обратите внимание, что вы заинтересованы в поиске значения, а не ключа)