Finding closes values from dictionary

Question

Hello I'm trying to find closest values(which needs to be 2) from dictionary, by specified value, but seems I'm not able to find working solution.

Tried to use for first time tryied to find values using static range, but realised if value diffrence is higher than specified range my code will return wrong values so I forced to return to "drawing board"

Dictionary<double,double> valueDictionary = new Dictionary<double, double>();
valueDictionary.Add(0,10);
valueDictionary.Add(1, 25);
valueDictionary.Add(2, 35);
valueDictionary.Add(3, 55);
valueDictionary.Add(4, 100);


double valueToFind = 40;
var result = valueDictionary.Values.Where(t => t >= valueToFind - 10 && t <= valueToFind + 10).ToDictionary(t=> t,v=>v);
Debug.WriteLine("Result "+result.Count);

If we searching for value 40, then it has to return 35 and 55

valueDictionary.Add(2, 35);
valueDictionary.Add(3, 55);

If we searching for value 60, then it has to return 55 and 100

valueDictionary.Add(3, 55);
valueDictionary.Add(4, 100);

But if we searching for value 55, then its has to return it index id which are 3

Thanks for help.

Not a best solution but it does its job, just wondering is this would be possible to use linq on this solution

double valueToFind = 40;

MyObject minimum = new MyObject(){Y= 0,X = 0};// define minimum range
MyObject maximum = new MyObject(){Y = 100, X = 100}; //define maximum range

foreach (var child in tempList)//your collection
{
    if (child.X <= valueToFind)// try to find lower values from our valueToFind variable
    {
         if (child.Y >= minimum.X)//if value is higher than our lower value, it means its close to our searching minimum value
         {
                        minimum.Y = child.Y;
                        minimum.X = child.X;
         }
    }
    else if (child.X >= valueToFind) // try to find higher values from our valueToFind variable
    {
         if (child.X <= maximum.X) //if value is lower than our higher value, it means its close to our searching maximum value
         {
               maximum.Y = child.Y;
               maximum.X = child.X;
         }
    }
  }

Debug.WriteLine("Found variables");
Debug.WriteLine(minimum.X + " " + minimum.Y);
Debug.WriteLine(maximum.X + " " + maximum.Y);

public class MyObject
{
   public double X { get; set; }

   public double Y { get; set; }
}

Does one have to be above and one have to be below the requested value? If not, you could use something like `OrderBy(x => Math.Abs(x.Value - valueToFind)).Take(2)` — Matthew, Mar 27 '19 at 17:31
Yes it has to select lower and higher values from searching values — Joel2, Mar 27 '19 at 17:32
You can probably use `OrderBy` twice to find the closest values above and below, and take the first one. — Matthew, Mar 27 '19 at 17:33
Why you a dictionary for this kind of task? Do you really need the key that is associated with each value or simply its position in the sequence? — haim770, Mar 27 '19 at 17:40
Dictionary was selected since index and value was easy to access, no extra code needed, @Matthew tried your code and if I have values 0 20 and 100 if I searching it would return 0 and 20 instead 20 and 100 — Joel2, Mar 27 '19 at 17:45
Assuming your data is always sorted, you can use a slightly modified version of a binary-search algorithm to check the previous and next item in the sequence and return them in case your searched value falls in their range — haim770, Mar 27 '19 at 18:54
`List.BinarySearch` seems like it might be what you want - is the index arbitrary, increasing sequential number? — NetMage, Mar 27 '19 at 19:03

NetMage · Accepted Answer · 2019-03-28T17:49:09.633

2

Using List.BinarySearch, you can find either a matching value or the nearest values:

var values = new List<double>() { 10, 25, 35, 55, 100 };

var valueToFind = 60.0;

var findIndex = values.BinarySearch(valueToFind);
double lowValue, highValue;

bool found = findIndex >= 0;
if (!found) {
    var highIndex = -findIndex - 1;
    var lowIndex = Math.Max(highIndex - 1, 0);
    highIndex = Math.Min(highIndex, values.Count - 1);
    lowValue = values[lowIndex];
    highValue = values[highIndex];
}

NOTE: The List must be sorted for BinarySearch to work.

edited Mar 28 '19 at 17:49

answered Mar 27 '19 at 19:39

NetMage

26,163
3
34
55

if found true it means it has valid index? – Joel2 Mar 28 '19 at 12:46
Yes, when [`BinarySearch`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.binarysearch?view=netframework-4.7.2#System_Collections_Generic_List_1_BinarySearch__0_) returns a non-negative value, that means the index for the search item was found. Note the caveat about needing a sorted `List`. – NetMage Mar 28 '19 at 17:48
If you build the list dynamically, [this](https://stackoverflow.com/a/46294791/2557128) will prove helpful. – NetMage Mar 28 '19 at 18:01

score 1 · Answer 2 · answered Mar 28 '19 at 12:22

This is my attempt:

var values = new List<int>() {10, 25, 35, 55, 100};

var valueToFind = 60;
// For the index, simply do FindIndex().
// Will be -1 in case we don't find the value.
int foundIndex = values.FindIndex(v => v == valueToFind);

// Sort by absolute difference with the valueToFind
var sorted = values
    .OrderBy(v => Math.Abs(v - valueToFind)) 
    .Select(v => (int?) v); // Just so we can get nulls from FirstOrDefault() later

// Take the first less-than value, or null
var less = sorted.FirstOrDefault(v => v < valueToFind);

// Take the first greater-than value, or null
var greater = sorted.FirstOrDefault(v => v > valueToFind);

You then would need to conduct an extra check - to see if foundIndex is -1, and maybe omit the search for the greater altogether in case it's not needed.

Finding closes values from dictionary

2 Answers2