1
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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

groupby

where

struct Foo
{
    public string Id;
    public double Value;
}
\$\endgroup\$
  • \$\begingroup\$ 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 ? \$\endgroup\$ – Sugat Oct 31 '16 at 19:46
  • \$\begingroup\$ @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. \$\endgroup\$ – t3chb0t Oct 31 '16 at 20:05
  • \$\begingroup\$ 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. \$\endgroup\$ – t3chb0t Oct 31 '16 at 20:07
  • \$\begingroup\$ Oh I see it now. As I will have more duplicates, it will be more efficient. Thanks. \$\endgroup\$ – Sugat Nov 1 '16 at 16:54
0
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ Can you please define what first and second variables are ? Thanks for the reply. \$\endgroup\$ – Sugat Oct 31 '16 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.