0

This is related to Equivalent of Java's SortedMap.tailMap in C# SortedDictionary, but my requirement is slightly different so I'm hoping there might be a better solution.

I have a SortedDictionary, and I have a key value K which is not present in the dictionary. I want to find the nearest keys above and below K that ARE present.

With a Java TreeMap, I can do this using the floorKey() and ceilingKey() methods.

I know that I can efficiently get the sorted list of keys present in the dictionary, but that doesn't seem to help me.

(a) Is there a way of doing this efficiently with a SortedDictionary?

(b) If not, is there a different collection class I can use? (I obviously need the standard functionality of SortedDictionary as well)

Michael Kay
  • 156,231
  • 11
  • 92
  • 164
  • Well, if it's up to date then it confirms that there's no easy off-the-shelf solution. (Also, that question was looking for the predecessor of a key that is actually present, whereas I'm looking for the predecessor of an absent key, so some of the suggested approaches in that question don't work.) – Michael Kay May 06 '21 at 08:33
  • [SortedDictionary](https://referencesource.microsoft.com/#System/compmod/system/collections/generic/sorteddictionary.cs,07052c0941912f81) is wrapper to a [TreeSet](https://referencesource.microsoft.com/#System/compmod/system/collections/generic/sorteddictionary.cs,07052c0941912f81,references) that is a [SortedSet](https://referencesource.microsoft.com/#System/compmod/system/collections/generic/sortedset.cs,6f4f66b9b70e07ba) managed as nodes left and right with unique parent. It is more a set like in math theory, ordered like a linked list, and not a list like an array. –  May 06 '21 at 08:42
  • [Comparative Analysis of List, HashSet and SortedSet](https://www.c-sharpcorner.com/UploadFile/0f68f2/comparative-analysis-of-list-hashset-and-sortedset/) –  May 06 '21 at 08:44
  • If you can use `SortedList` instead, then its `Keys` property is an ordered `IList` so you can perform a binary search on it. For some better performance (but it depends on the actual use case) you can also try my [`CircularSortedList`](https://github.com/koszeggy/KGySoft.CoreLibraries/blob/master/KGySoft.CoreLibraries/Collections/CircularSortedList.cs). See the *Remarks* section of the [docs](http://docs.kgysoft.net/corelibraries/?topic=html/T_KGySoft_Collections_CircularSortedList_2.htm) for a comparison table, which may help to choose the best type for your needs. – György Kőszeg May 06 '21 at 09:30
  • @GyörgyKőszeg Thanks for the suggestion of using a `SortedList` in place of a `SortedDictionary`. I think I may be able to do that. – Michael Kay May 06 '21 at 11:16
  • Some people on SO seem a bit over-enthusiastic about closing as a duplicate. The question cited is sufficiently different that several of the proposed answers are not at all applicable, although some suggest ideas that can be extrapolated to this problem. – Michael Kay May 07 '21 at 14:11

1 Answers1

-1

Array.BinarySearch(...) sounds like it does what you want. https://learn.microsoft.com/en-us/dotnet/api/system.array.binarysearch?view=net-5.0

Here is an example for finding the largest item that is smaller than a specified item.

T[] array = ...; // array must be sorted and T must implement IComparable<T>
T item = ...; // item that you are trying to find in array

int index = Array.BinarySearch(array, item);
if (index < 0)
{
    // item not found
    // index represents the bitwise complement of the next larger element in the array
    index = ~index;
    if (index == 0)
    {
        // specified item is less than the smallest item in the array
    }
    else
    {
        // array[index - 1] is the largest item that is less than the specified item
    }
}
else
{
    // array[index] is the specified item
}
ElGordo
  • 193
  • 1
  • 7