Find next value from List of tuples in C#-CodePudding

So this is out of my acknowledge, maybe some of you can help me.

I have a list with 2 columns. myList, as you can see in the example, will be short and has the first column sorted.

private List<(double,double)> myList = new List<(double column1, double column2)> {
    (6,80),
    (8,107),
    (10,134),
    (12,160),
    (16,214),
    (20,267),
    (25,334),
    (32,427),
    (40,534)
};

What I need to do is, given a number, let's say 24. Search the next closest value from the list of tuples and return the correct tuple. So it should return (25,334).

If the target is 21, the desired result is (25,334).

My first approach was using lists as I might Add some values in the future. But if you know any kind of struct that adjusts better to this kind of usage, be free to propose.

Thanks in advance

CodePudding user response：

If the list is sorted, you can find this element with

var (x, y) = myList.FirstOrDefault(t => t.Item1 >= 24);

If no such element is found, then x will be 0 and otherwise the required value (x = 25 in this example and y = 334).

CodePudding user response：

Given that your list of tuples is sorted, you can use binary search to find the index of the item matching or following the target. This has O(Log(N)) complexity, so it's quite efficient:

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    static class Program
    {
        public static void Main()
        {
            List<(double, double)> myList = new List<(double column1, double column2)> {
                (6,80),
                (8,107),
                (10,134),
                (12,160),
                (16,214),
                (20,267),
                (25,334),
                (32,427),
                (40,534)
            };

            double target = 24;

            int index = myList.BinarySearch(
                (target, 0), 
                Comparer<(double, double)>.Create(
                    (lhs, rhs) => lhs.Item1.CompareTo(rhs.Item1)) );

            if (index < 0)
                index = ~index;

            if (index < myList.Count)
                Console.WriteLine($"Found at index {index}, value = {myList[index]}");
            else
                Console.WriteLine("Not found");
        }
    }
}

Try it on DotNetFiddle

One bit of fiddlyness is the way that the index is returned by BinarySearch() if the item is not found. It will be negative in that event, and you have to take the bitwise not to get the index of the next value. Don't blame me for this. ;)

Another bit of fiddlyness is that you are searching only for the first item in the tuple, so the second is effectively ignored.

Finally, if the item is not found the index will be one beyond the end of the list, so you must account for that too.

CodePudding user response：

find the closest value from the list:

 var result=myList.OrderBy(item => Math.Abs(number - item.Item1)).First();

find the next closest value from the list:

var result = myList.First(item => item.Item1-number>=0);

CodePudding user response：

One of you answered my question and then deleted the post. I'm not the author of the solution!

double target = 21;
var closest = myList.MinBy(item => Math.Abs(item.Item1 - target));
double resultValue = closest.Item2;

The result value is 334.

This is what I wanted to do and in just one line. Beautiful

Thanks!