Finding closest match in collection of numbers [cl

Question

So I got asked today what was the best way to find the closes match within a collection.

For example, you've got an array like this:

1, 3, 8, 10, 13, ...

What number is closest to 4?

Collection is numerical, unordered and can be anything. Same with the number to match.

Lets see what we can come up with, from the various languages of choice.

Answer 1

PostgreSQL:

select n from tbl order by abs(4 - n) limit 1

In the case where two records share the same value for "abs(4 - id)" the output would be in-determinant and perhaps not a constant. To fix that I suggest something like the untested guess:

select n from tbl order by abs(4 - n) + 0.5 * 4 > n limit 1;

This solution provides performance on the order of O(N log N), where O(log N) is possible for example: https://stackoverflow.com/a/8900318/1153319

Answer 2

int numberToMatch = 4;

var closestMatches = new List<int>();
closestMatches.Add(arr[0]); // closest tentatively

int closestDifference = Math.Abs(numberToMatch - arr[0]);


for(int i = 1; i < arr.Length; i++)
{
    int difference = Math.Abs(numberToMatch - arr[i]);
    if (difference < closestDifference)
    {
        closestMatches.Clear();
        closestMatches.Add(arr[i]);
        closestDifference = difference;
    }
    else if (difference == closestDifference)
    {       
        closestMatches.Add(arr[i]);
    }
}


Console.WriteLine("Closest Matches");
foreach(int x in closestMatches) Console.WriteLine("{0}", x);

Answer 3

Some C# Linq ones... too many ways to do this!

decimal[] nums = { 1, 3, 8, 12 };
decimal target = 4;

var close1 = (from n in nums orderby Math.Abs(n-target) select n).First();
var close2 = nums.OrderBy(n => Math.Abs(n - target)).First();

Console.WriteLine("{0} and {1}", close1, close2);

Even more ways if you use a list instead, since plain ol arrays have no .Sort()

Answer 4

Python by me and https://stackoverflow.com/users/29253/igorgue based on some of the other answers here. Only 34 characters:

min([(abs(t-x), x) for x in a])[1]

Answer 5

Some of you don't seem to be reading that the list is unordered (although with the example as it is I can understand your confusion). In Java:

public int closest(int needle, int haystack[]) { // yes i've been doing PHP lately
  assert haystack != null;
  assert haystack.length; > 0;
  int ret = haystack[0];
  int diff = Math.abs(ret - needle);
  for (int i=1; i<haystack.length; i++) {
    if (ret != haystack[i]) {
      int newdiff = Math.abs(haystack[i] - needle);
      if (newdiff < diff) {
        ret = haystack[i];
        diff = newdiff;
      }
    }
  }
  return ret;
}

Not exactly terse but hey its Java.

Answer 6

Language: C, Char count: 79

c(int v,int*a,int A){int n=*a;for(;--A;++a)n=abs(v-*a)<abs(v-n)?*a:n;return n;}

Signature:

int closest(int value, int *array, int array_size);

Usage:

main()
{
    int a[5] = {1, 3, 8, 10, 13};
    printf("%d\n", c(4, a, 5));
}