How do you search a collection for a key, and get the next highest item if it doesn't exist?

Question

How, in a .NET, do you search a sorted collection for a key, and get the index, or if it doesn't exist, get the index of the next highest item?

For example there is a list that contains elements {1,5,8,10}. I search for 7. It doesn't exist, but the next highest key that does exist is 8 with an index of 2.

Example:

SortedList<int, int> list = new SortedList<int, int>();
list.Add(1, 1);
list.Add(5, 1);
list.Add(8, 1);
list.Add(10, 1);

int index = list.IndexOfKeyOrNext(7); // theoretical function. returns 2

I can do this by adding a temporary item at 7, calling list.IndexOfKey(7), then removing my temporary item. But This is slow. Is there a better way?

Edit: My list is sorted.

Answer 1

If you are only ever doing this to a sorted list, then I propose using a custom variant of the Binary Search algorithm: If you don't find the element you are looking for, then your upper bound actually contains the index of the next item in the list.

In your example, the algorithm would start out with

lowerBound = 0
upperBound = 3

Both of them index values that are not what you are looking for (1 and 10). Thus, you want to check the two halves 0, 1 and 2, 3 - this is where you modify the standard algorithm - since it is in neither, you can assume that the first element in the second half is the next greater item, its index being the lower bound of the second half (2).

This should give you an efficiency of O(log(n)).

Answer 2

int yourValue = 5;

var item = list.FirstOrDefault(x => x >= yourValue);

if(item != null)
{
  var index = list.IndexOf(item);
}

This assumes your list is presorted, and that you're able to use Linq.

Answer 3

If you're using List<T> instead of SortedList and make sure it is sorted, you can do this using the BinarySearch method.

It returns the index of the element or the bitwise complement to the index where the value would be found if it was there. You can use this to find the next highest element. The code would be something like this

var index = list.BinarySearch(7);
if (index >= 0) {
   Console.WriteLine("found value");
} else {
   Console.WriteLine("next value is {0}", list[~index + 1]);
}

Answer 4

A modified binary search would be the fastest way. A binary search is an O(log n) operation, so it's much faster than looping through all the items to find a match.

public int IndexOfKeyOrNext(SortedList<int,int> list, int find) {
   int first = 0;
   int last = list.Count - 1;
   while (first < last) {
      int pos = first + last / 2;
      if (list.Keys[pos].Key < find) {
         first = pos + 1;
      } else {
         last = pos;
      }
   }
   if (first < list.Count && list.Keys[first] >= find) {
      return first;
   } else {
      return -1;
   }
}