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

Question

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>();
            sampleClassList.Add(input1);
            sampleClassList.Add(input2);
            sampleClassList.Add(input3);
            sampleClassList.Add(input4);
            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?

Answer 1

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;
}

Answer 2

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;