I have a sorted list of key/value pairs, and want to find the values adjacent to a new key

Question

I have a list of key/value pairs (probably will be using a SortedList) and I won't be adding new values.

Instead I will be using new keys to get bounding values. For example if I have the following key/value pairs:

(0,100) (6, 200), (9, 150), (15, 100), (20, 300) 

and I have the new key of 7, I want it to return 200 and 150, because 7 is between 6 and 9.

If I give 15 I want it to return 100 and 100 (because 15 is exactly 15). I want something like a binary search.

Thanks

Answer 1

Yep, you want exactly binary search -- use the List<t>.BinarySearch method, specifically the overload taking a IComparer second argument (and implement that interface with a simple aux class that just compares keys).

Answer 2

You can do this with List<T>.BinarySearch:

var keys = new List<int>(sortedList.Keys);
int index = keys.BinarySearch(target);
int lower;
int upper;
if (index >= 0) {
  lower = upper = index;
}
else {
  index = ~index;
  upper = index < keys.Count ? index : index - 1;
  lower = index == 0 ? index : index - 1;
}

Console.WriteLine("{0} => {1}, {2}", 
  target, sortedList[keys[lower]], sortedList[keys[upper]]);

You have to use the return value of List<T>.BinarySearch to get to the boundary values. From msdn, its return value is:

"The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count."

Also, for elements that fall below the first or beyond the last, this code "returns" the first and the last twice, respectively. This might not be what you want, but it's up to you to define your boundary conditions. Another one is if the collection is empty, which I didn't address.