¿Hay una función de límite inferior en una SortedList ?

¿Hay una función de límite inferior en una SortedList ? La función debe devolver el primer elemento igual o superior a la clave especificada. ¿Hay alguna otra clase que apoye esto?

Chicos, por favor, lean la pregunta una vez más. No necesito una función que devuelva la clave si está presente. Me interesa el escenario cuando no coinciden las claves exactas.

Estoy interesado en el tiempo O (log n) . Significa que no tengo un problema con foreach loop, pero me gustaría tener una forma eficiente de hacerlo.

He hecho algunas pruebas sobre esto.

Los enunciados de Linq no son optimizados ni por el comstackdor ni por la máquina de tiempo de ejecución, por lo que recorren todos los elementos de la colección y son lentos O (n). Según la respuesta de Mehrdad Afshari, aquí hay una búsqueda binaria que funciona en O (log n) en la colección Keys:

 public static int FindFirstIndexGreaterThanOrEqualTo( this IList sortedCollection, T key ) where T : IComparable { int begin = 0; int end = sortedCollection.Count; while (end > begin) { int index = (begin + end) / 2; T el = sortedCollection[index]; if (el.CompareTo(key) >= 0) end = index; else begin = index + 1; } return end; } 

Búsqueda binaria de la colección SortedList.Keys .

Aquí vamos. Esto es O (log n ):

 private static int BinarySearch(IList list, T value) { if (list == null) throw new ArgumentNullException("list"); var comp = Comparer.Default; int lo = 0, hi = list.Count - 1; while (lo < hi) { int m = (hi + lo) / 2; // this might overflow; be careful. if (comp.Compare(list[m], value) < 0) lo = m + 1; else hi = m - 1; } if (comp.Compare(list[lo], value) < 0) lo++; return lo; } public static int FindFirstIndexGreaterThanOrEqualTo (this SortedList sortedList, T key) { return BinarySearch(sortedList.Keys, key); } 

Me gustaría ir con LINQ (suponiendo que estés usando C # 3), pero usando la sobrecarga de FirstOrDefault que toma un predicado:

 first = sortedList.FirstOrDefault(x => x >= theObjectForComparison); 

(muchos de los otros métodos Enumerables también pueden tomar predicados, lo cual es un buen atajo)

No estoy enterado de uno, pero es una statement LINQ simple:

 first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault(); 

first será el primer objeto que pase la comparación o por default(T) (que normalmente es null ).

Editar

La versión de DaveW:

 first = sortedList.FirstOrDefault(x => x >= theObjectForComparison); 

hace el mismo trabajo pero podría ser más rápido, sin embargo, tendría que probarlo.

O puede escribir su propio método de extensión para hacer esto. Tenga en cuenta que no se garantiza que todas esas funciones entren en un enclaustramiento.

Con suerte, esto debería ser más rápido, según la implementación de SortedList.

 public static int FindFirstIndexGreaterThanOrEqualTo( this SortedList sortedCollection, K key ) where V : new() { if (sortedCollection.ContainsKey(key)) { return sortedCollection.IndexOfKey(key); } sortedCollection[key] = new V(); int retval = sortedCollection.IndexOfKey(key); sortedCollection.Remove(key); return retval; }