Find the nearest number in the list of numbers

Question

I have a list of constant numbers. I need to find the closest number to x in the list of numbers. Any ideas on how to implement this algorithm?

Answer 1

Well, you can't do it faster than O(N) , because you need to check all the numbers to make sure you have the closest one. However, why not use the simple minimum search option, looking for the one with the smallest absolute difference with x?

If you can say that the list is ordered from the very beginning (and it allows random access, such as an array), then the best approach is to use binary search. When you finish searching on index i (without finding x), simply select the best from this element and its neighbors.

Answer 2

I assume the array is unordered. When ordering, it can be faster

I think the easiest and fastest way is to use a linear algorithm to find the minimum or maximum, but instead of comparing the values, you compare the absolute value of the difference between this and the needle.

In C ++ (I cannot C #, but it will be similar) the code may look like this:

 // array of numbers is haystack // length is length of array // needle is number which you are looking for ( or compare with ) int closest = haystack[0]; for ( int i = 0; i < length; ++i ) { if ( abs( haystack[ i ] - needle ) < abs( closest - needle ) ) closest = haystack[i]; } return closest; 

Answer 3

In general, people on this site will not do their homework for you. Since you did not send the code, I will not send the code either. However, one of the possible approaches is possible here.

Scroll through the list by subtracting the number from the list from x. Take the absolute value of this difference and compare it with the best previous result you received, and if the current difference is less than the best previous result, save the current number from the list. At the end of the cycle you will receive an answer.

Answer 4

 private int? FindClosest(IEnumerable<int> numbers, int x) { return (from number in numbers let difference = Math.Abs(number - x) orderby difference, Math.Abs(number), number descending select (int?) number) .FirstOrDefault(); } 

Zero means there was no nearest number. If there are two numbers with the same difference, he will choose the closest to zero. If two numbers are at the same distance from zero, a positive number will be selected.

Edit in response to Eric's comment:

Here is a version that has the same semantics, but uses the Min operator. This requires an implementation of IComparable<> , so we can use Min , keeping the number that goes with each distance. I also made it an extension for ease of use:

 public static int? FindClosestTo(this IEnumerable<int> numbers, int targetNumber) { var minimumDistance = numbers .Select(number => new NumberDistance(targetNumber, number)) .Min(); return minimumDistance == null ? (int?) null : minimumDistance.Number; } private class NumberDistance : IComparable<NumberDistance> { internal NumberDistance(int targetNumber, int number) { this.Number = number; this.Distance = Math.Abs(targetNumber - number); } internal int Number { get; private set; } internal int Distance { get; private set; } public int CompareTo(NumberDistance other) { var comparison = this.Distance.CompareTo(other.Distance); if(comparison == 0) { // When they have the same distance, pick the number closest to zero comparison = Math.Abs(this.Number).CompareTo(Math.Abs(other.Number)); if(comparison == 0) { // When they are the same distance from zero, pick the positive number comparison = this.Number.CompareTo(other.Number); } } return comparison; } } 

Answer 5

This can be done using a SortedList :
Blog post about finding the nearest number
If the complexity you are looking for takes into account only the complexity search, this is O (log (n)). List line will cost O (n * log (n))

If you are going to insert an item in the list much more than you want to request it for the nearest number, the best choice is to use the List and use the naive algorithm to request it for the nearest number. Each search will cost O (n), but the time to insert will be reduced to O (n).

General difficulty: if the collection has n numbers and is searched q times -
List: O(n+q*n)
Sorted list: O(n*log(n)+q*log(n))

A value from some q sorted list will provide better complexity.

Answer 6

Being lazy, I did not test this, but should not this work

 private int FindClosest(IEnumerable<int> numbers, int x) { return numbers.Aggregate((r,n) => Math.Abs(rx) > Math.Abs(nx) ? n : Math.Abs(rx) < Math.Abs(nx) ? r : r < x ? n : r); } 

Answer 7

Haskell:

 import Data.List (minimumBy) import Data.Ord (comparing) findClosest :: (Num a, Ord a) => a -> [a] -> Maybe a findClosest _ [] = Nothing findClosest n xs = Just $ minimumBy (comparing $ abs . (+ n)) xs 

Answer 8

  Performance wise custom code will be more use full. List<int> results; int targetNumber = 0; int nearestValue=0; if (results.Any(ab => ab == targetNumber )) { nearestValue= results.FirstOrDefault<int>(i => i == targetNumber ); } else { int greaterThanTarget = 0; int lessThanTarget = 0; if (results.Any(ab => ab > targetNumber )) { greaterThanTarget = results.Where<int>(i => i > targetNumber ).Min(); } if (results.Any(ab => ab < targetNumber )) { lessThanTarget = results.Where<int>(i => i < targetNumber ).Max(); } if (lessThanTarget == 0 ) { nearestValue= greaterThanTarget; } else if (greaterThanTarget == 0) { nearestValue= lessThanTarget; } else if (targetNumber - lessThanTarget < greaterThanTarget - targetNumber ) { nearestValue= lessThanTarget; } else { nearestValue= greaterThanTarget; } }