How to get the closest number from a List with LINQ?

Question

How to get the closest number from a List<int> with LINQ?

For example:

List<int> numbers = new List<int>();
numbers.Add(2);
numbers.Add(5);
numbers.Add(7);
numbers.Add(10)

I need to find the closest value in the list to number 9. In this case 10.

How can I do this with LINQ?

Any kind of code you could provide always helps get your question understood and thusly answered. :) — Mike Fielden, May 10 '11 at 16:57
Is the list known to be in order? Does the list contain duplicates? What should happen if more than one number is "closest"? How big is the list likely to be? — Eric Lippert, May 10 '11 at 18:07
The last case mentioned is exceptionally interesting. None of the provided answers seem to be easily manipulated into being 'stable' in a sense that the larger or smaller number is returned consistently. — Beltway, Mar 16 '22 at 11:39

score 161 · Accepted Answer · edited Jun 10 '11 at 07:04

161

If you use LINQ to Objects and the list is long, I would use:

List<int> list = new List<int> { 2, 5, 7, 10 };
int number = 9;

int closest = list.Aggregate((x,y) => Math.Abs(x-number) < Math.Abs(y-number) ? x : y);

This method is slightly more complex than the solution that Anthony Pegram suggested, but it has as advantage that you don't have to sort the list first. This means that you have a time complexity of O(n) instead of O(n*log(n)) and a memory usage of O(1) instead of O(n).

edited Jun 10 '11 at 07:04

Peter Mortensen

30,738
21
105
131

answered May 10 '11 at 17:33

Elian Ebbing

18,779
5
48
56

thanks for the answer, so, I don't understand this part: ? x : y, what is the meaning of that? – ale May 10 '11 at 18:15
1

That's the condition operator. See http://msdn.microsoft.com/en-us/library/ty67wk28.aspx. I use it to choose `x` or `y`, depending on which one is closest to `number`. – Elian Ebbing May 10 '11 at 18:28
how to find out about the index too? index of the closet number?? – user7157732 Jan 26 '17 at 16:13

score 49 · Answer 2 · answered May 10 '11 at 17:15

49

If you want to use LINQ to perform this task, you can do it like below.

List<int> list = new List<int> { 2, 5, 7, 10 };
int number = 9;

// find closest to number
int closest = list.OrderBy(item => Math.Abs(number - item)).First();

answered May 10 '11 at 17:15

Anthony Pegram

123,721
27
225
246

7

The disadvantage of this solution is that it has to order the list first, which hurts performance if the list is long. See my answer for a solution that returns the value in `O(n)` time. – Elian Ebbing May 10 '11 at 17:36
1

@Elian, I agree. Mine is perhaps more readable. I would have argued for a general loop to avoid LINQ entirely if performance was not good enough, but I have my own job to do. ;) – Anthony Pegram May 10 '11 at 17:48
3

I would prefer to use LINQ instead of extension methods. However, this is still beautiful code. No premature optimization, just simple clean code. + for that. – Steven May 10 '11 at 18:50

score 6 · Answer 3 · edited Apr 18 '17 at 10:49

6

The solutions above are all O(N) at best.

If you have a big list and you perform this closest-element query multiple times, it would be more performant to sort the list first ( O(NlogN) ) and then use List<T>.BinarySearch for each query. The performance for k queries is O( (k+N)logN ), in comparison to O(kN) of the previous method.

edited Apr 18 '17 at 10:49

Liam

27,717
28
128
190

answered Sep 10 '16 at 11:14

Theodore Zographos

2,215
1
24
23

score 4 · Answer 4 · answered Jul 29 '20 at 09:07

4

These days there also exist a nice and simple option:

List<int> list = new List<int> { 2, 5, 7, 10 };
int number = 9;

int min = list.Min(i => (Math.Abs(number - i), i)).i;

answered Jul 29 '20 at 09:07

Lev

811
12
13

score -1 · Answer 5 · answered Dec 11 '16 at 02:11

-1

You could you the binary search. It is the build in method in c# that will help you search for the number closest. Here example: https://msdn.microsoft.com/en-us/library/y15ef976(v=vs.110).aspx

answered Dec 11 '16 at 02:11

A. Randhawa

49
4

1

A binary search requires the list to be sorted first, and that can hurt performance. – SneakyTactician Jul 05 '17 at 15:43

score -5 · Answer 6 · edited Feb 17 '22 at 07:43

-5

Use this get nearest lower or Higher based on condition You used.

 List<int> list = new List<int> { 2, 5, 7, 10 };
 int number = 9;
 var closest = list.Where(numbers => numbers > number).First();
 Console.WriteLine(closest);
 Console.ReadLine();

edited Feb 17 '22 at 07:43

Alp

358
5
12

answered Sep 10 '16 at 12:00

TAMIL ARASAN

37
3

This returns the wrong result if the match is not below the searched number. In the example, if you search for 8, 10 would be returned. – Heiner Nov 26 '18 at 16:20

How to get the closest number from a List with LINQ?

6 Answers6

Linked