# C# Code Optimization — Finding nearest key in a SortedList

Just wondering if anyone can see a way to optimize this piece of code. It is a key piece of my program and needs to run as quickly as possible. The part of the code I am unsure of is the while loop for finding the nearest key -- but any assistance with optimizing the code would be appreciated.

// TODO: Move to snippets lib or create a new collection type that supports this feature
private string _getTrait(SortedList<decimal, string> thisList, decimal thisValue)
{
// Check to see if we need to search the list.
if (thisList == null || thisList.Count <= 0) { return null; }
if (thisList.Count == 1) { return thisList.Values[0]; }

// Setup the variables needed to find the closest index
int lower = 0;
int upper = thisList.Count - 1;
int index = (lower + upper) / 2;

// Find the closest index (rounded down)
bool searching = true;
while (searching)
{
int comparisonResult = Decimal.Compare(thisValue, thisList.Keys[index]);
if (comparisonResult == 0) { return thisList.Values[index]; }
else if (comparisonResult < 0) { upper = index - 1; }
else { lower = index + 1; }

index = (lower + upper) / 2;
if (lower > upper) { searching = false; }
}

// Check to see if we are under or over the max values.
if (index >= thisList.Count - 1) { return thisList.Values[thisList.Count - 1]; }
if (index < 0) { return thisList.Values[0]; }

// Check to see if we should have rounded up instead
if (thisList.Keys[index + 1] - thisValue < thisValue - (thisList.Keys[index])) { index++; }

// Return the correct/closest string
return thisList.Values[index];
}


I am using C#, .net4.0 -- I need to use a Generic SortedList ( http://msdn.microsoft.com/en-US/library/ms132319(v=vs.100).aspx )

-
unrelated: I'm curious to know what a method beginning with an underscore means in your codebase. –  crdx Nov 2 '12 at 16:35
This code runs extremely fast, even for big lists. I strongly doubt that this is your bottleneck. –  codesparkle Nov 2 '12 at 17:27
@crdx anything with an _ in my database designates it as private. Just makes it easy to find the stuff I want when coding. –  Anthony Nichols Nov 2 '12 at 18:15
@codesparkle -- thanks for the insight, I still consider myself a novice when it comes to programming. The code looks messy to me and I felt there had to be better way to do it... Maybe I am lacking confidence rather than optimization. –  Anthony Nichols Nov 2 '12 at 18:18
Optimization starts with profiling. Don't guess where the bottlenecks are, know it. –  ANeves Nov 2 '12 at 20:16

Your loop is pretty well written. The only thing that sticks out to me is your use of a constant in the while loop and manually breaking. I also prefer to use a slightly different version of CompareTo, but it doesn't make much difference:

while ( (lower<=upper))
{
int comparisonResult = thisValue.CompareTo( thisList.Keys [index]);
if (comparisonResult == 0) { return thisList.Values[index]; }

if (comparisonResult < 0)
{
upper = index - 1;
}
else
{
lower = index + 1;
}
index = (lower + upper) / 2;
}


You might also be looking for a solution that's just easier to read or shorter. Are you familiar with LINQ? This is one possibility for how your function might look.

    private static string GetTraitRefactor (SortedList<decimal, string> thisList, decimal thisValue)
{
var keys = thisList.Keys;
var nearest = thisValue -
keys.Where(k => k <= thisValue)
.Min(k => thisValue - k);
return thisList[nearest];
}

-
I have the constant bool in there because I need to update the index before it breaks, without the bool I think the index would miss the last update... Maybe I am wrong on that; I will try it a bit later. –  Anthony Nichols Nov 2 '12 at 23:26
Also, I know a little bit about LINQ but still learning. That looks like something that might be worth plugging in and seeing how it runs. –  Anthony Nichols Nov 2 '12 at 23:28
Marking this as the answer as it's the only one that I got -- thanks. While I didn't user any of the code provided you made me feel more confidant about my code and gave me some alternatives to work through. Thanks! –  Anthony Nichols Nov 3 '12 at 18:17
Like I mentioned, your loop is well coded and straightforward enough that there's not too much to do with it. –  Reacher Gilt Nov 5 '12 at 16:16