# Finding the closest value and matching it with the correct item in the list

I have list values with their IDs like this:

ID   Value
A    1.2
B    4.2
C    7.2
D    10.2


In C#, I want to find the ID with the closest value to a given value say 3.9. In this example, B will be the answer as it has the value(4.2) closest to the given value.

My solution to this problem involved following steps:

• Put the values in an list of objects (where each object has a property ID and a value) or a dictionary with string ID and decimal value
• Loop through the list or dictionary and find the minimum value
• If the value is found or their difference is minimum, print the item ID (in this case B)

I want to know if there is better solution in terms of time complexity as here it seems to be $O(n)$.

public class SampleClass {
public string ID { get; set; }
public double Value { get; set; }
public SampleClass(string _id, double _value){
this.ID = _id;
this.Value = _value;
}
public static void Main(string[] args){
SampleClass input1 = new SampleClass("A",1.20);
SampleClass input2 = new SampleClass("B", 4.20);
SampleClass input3 = new SampleClass("C", 7.20);
SampleClass input4 = new SampleClass("D", 10.20);
double givenValue = 9.9;
List<SampleClass> sampleClassList = new List<SampleClass>();
double cVal = double.MaxValue;
string cID = string.Empty;
double diff = 0;
foreach (SampleClass item in sampleClassList){
if (item.Value == givenValue){
Console.WriteLine(item.ID);
return;
}
diff = Math.Abs(item.Value - givenValue);
if (diff < cVal) {
cVal = diff;
cID = item.ID;
}
}
Console.WriteLine(cID);
}
}


I am aware if there are list of values which is sorted, then you can find the closest value through binary search on this sorted list and it will give you a more efficient time complexity.

But in my case, after finding the closest value, I have to match this value to its ID. Also, these values can be duplicate, so I cannot use them as key in dictionary.

Is there more efficient way of doing this, or am I missing something?

You cannot use a dictionary but you can use the GroupBy and then search for the closest key. The values of the group will be the items with same values.

var values = new[]
{
new Foo{ Id ="A", Value = 1.2 },
new Foo{ Id ="B", Value = 4.2 },
new Foo{ Id ="C", Value = 7.2 },
new Foo{ Id ="D", Value = 4.2 }
}
.GroupBy(x => x.Value); where

struct Foo
{
public string Id;
public double Value;
}

• Hi, Thanks a lot for reply. Though I have a question regarding this method. How will it be better than O(n) average runtime ? GroupBy's average time complexity is O(n) and if I do binary search (whose complexity is log(n) on it after that, the total time complexity will be O(nlog(n)) which is almost equal ? Can you please kindly explain ? Oct 31, 2016 at 19:46
• @rPs the idea comes from this sentence But in my case, after finding the closest value, I have to match this value to its ID. Also, these values can be duplicate, so I cannot use them as key in dictionary. If you group the values then you'll find all IDs that belong to those values without having to scan each item. If you have a lot duplicate values then the search will still be O(n) but not of the original array but of the number of the keys of the groupping. If half of the values are duplicates then the search will be faster if performed several times for different values. Oct 31, 2016 at 20:05
• So you group the values once a reuse this groupping for subsequent searches. You then only need to search each value once, the more duplicates you have, the more efficient this will become. Oct 31, 2016 at 20:07
• Oh I see it now. As I will have more duplicates, it will be more efficient. Thanks. Nov 1, 2016 at 16:54

I think this will be a little more efficient

foreach(SampleClass sc in sampleClassList.OrderBy(x => x.Value).ThenBy(x => x.ID))
{
if(first == null)
{
if(givenValue >= sc.Value)
{
first = sc;
if (first.Value == givenValue)
{
Console.WriteLine(first.ID);
return;
}
}
}
else if (sc.Value >= givenValue)
{
second = sc;
diff1 = givenValue - first.Value;
diff2 = second.Value - givenValue;
if (diff1 <= diff2)
Console.WriteLine(first.ID);
else
Console.WriteLine(second.ID);
return;
}
}
if (first != null)
Console.WriteLine(first.ID);
else
Console.WriteLine("none");
return;

• Can you please define what first and second variables are ? Thanks for the reply. Oct 31, 2016 at 19:47