Generic SortedList, How to find the index of the first element that is greater than the search key?

Question

Without using extensions methods (LINQ). I am restricted to .NET 2.0 unfortunately. (Yeah, it sucks)

Looking for something close to O(log(n)).

Thanks for your help.

Answer 1

Since it's sorted, loop through and use Compare.

Update: Of course, that's assuming it's a list of Strings. If not, compare whatever it is that makes the current item less or greater than the search term and act accordingly.

Answer 2

Binary search it for an O(n log n) lookup.

Answer 3

To find the first key that is greater than a given key you could use the list of keys SortedList<T>.Keys and perform a Binary Search or Interpolation Search on the keys. This will yield O(log(n)) (MSDN states that a key look up is O(1)).

Answer 4

search where things are in oder O(log n) binary search

search for where things are not in order O(n) linear. Can't do better if things are not in order.

The idea of making the values in order by order takes O(n * log(n)) unless you are going to be doing this over and over and caching the result why bother? just use your linear search.

(note thought you were interested in searching the value not the key)