Find the closest number in a list of numbers

Question

I have a list of constant numbers. I need find the closest number to x, in the list of the numbers.

Any ideas on how to implement this alogrithm?

Thank You.

Answer 1

Well, you cannot do this faster than O(N) because you have to check all numbers to be sure you have the closest one. That said, why not use a simple variation on finding the minimum, looking for the one with the minimum absolute difference with x?

If you can say the list is ordered from the beginning (and it allows random-access, like an array), then a better approach is to use a binary search. When you end the search at index i (without finding x), just pick the best out of that element and its neighbors.

Answer 2

It can be done using SortedList:
Blog post on finding closest number
If the complexity you're looking for counts only the searching the complexity is O(log(n)). The list building will cost O(n*log(n))

If you're going to insert item to the list much more times than you're going to query it for the closest number then the best choice is to use List and use naive algorithm to query it for the closest number. Each search will cost O(n) but time to insert will be reduced to O(n).

General complexity: If the collection has n numbers and searched q times -
List: O(n+q*n)
Sorted List: O(n*log(n)+q*log(n))

Meaning, from some q the sorted list will provide better complexity.

Answer 3

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

Null means there was no closest number. If there are two numbers with the same difference, it will choose the one closest to zero. If two numbers are the same distance from zero, the positive number will be chosen.

Edit in response to Eric's comment:

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

public static int? FindClosestTo(this IEnumerable<int> numbers, int targetNumber)
{
    var minimumDistance = numbers.Select(number => new NumberDistance(x, 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 4

I suppose that the array is unordered. In ordered it can be faster

I think that the simpliest and the fastest method is using linear algorithm for finding minimum or maximum but instead of comparing values you will compare absolute value of difference between this and needle.

In the C++ ( I can't C# but it will be similar ) can code 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 5

In general people on this site won't do your homework for you. Since you didn't post code I won't post code either. However, here's one possible approach.

Loop through the list, subtracting the number in the list from x. Take the absolute value of this difference and compare it to the best previous result you've gotten and, if the current difference is less than the best previous result, save the current number from the list. At the end of the loop you'll have your answer.

Answer 6

Being lazy I have not check this but shouldn't this work

private int FindClosest(IEnumerable<int> numbers, int x)
{
    return
        numbers.Aggregate((r,n) => Math.Abs(r-x) > Math.Abs(n-x) ? n
                                 : Math.Abs(r-x) < Math.Abs(n-x) ? 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