Get nearest key above or below in a C# SortedDictionary

Question

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)

Answer 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
}