Binary Search on Keys of SortedList<K, V>

c# search performance sortedlist
Nitax picture Nitax · May 23, 2011 · Viewed 12.1k times · Source

I need to write some code for linear interpolation and I am trying to figure out the most efficient way to search the Keys of a SortedList<K, V> for the upper and lower keys that surround my target key.

SortedList<int, double> xyTable = new SortedList<int, double>()
{
    {1, 10}, {2, 20}, {3, 30}, {4,40}
};

double targetX = 3.5;

What is the most efficient way to search the list and determine that 3.5 is between 3 and 4? I have a method / cheat that works for integers (temporarily insert the target Key into the list then find the index) but I figured I'd ask the pros so I could produce quality code.

Thanks.

Answer

ColinE picture ColinE · May 23, 2011

A binary search gives you decent performance on a list. However the Keys property on SortedList is of type IList, whereas BinarySearch is defined on List. Fortunately, you can find an implementation of binary search for IList in this related question:

How to perform a binary search on IList<T>?

Related questions

Using C# to check if string contains a string in string array

I want to use C# to check if a string value contains a word in a string array. For example, string stringToCheck = "text1text2text3"; string[] stringArray = { "text1", "someothertext", etc... }; if(stringToCheck.contains stringArray) //one of the items? { } How can …

Read More
What .NET collection provides the fastest search

I have 60k items that need to be checked against a 20k lookup list. Is there a collection object (like List, HashTable) that provides an exceptionly fast Contains() method? Or will I have to write my own? In otherwords, is …

Read More
Case-Insensitive List Search

I have a list testList that contains a bunch of strings. I would like to add a new string into the testList only if it doesn't already exist in the list. Therefore, I need to do a case-insensitive search of …

Read More