views:

3923

answers:

28

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.

+1  A: 

EDITED = in the for loop

int Closest(int val, int[] arr)
{
    int index = 0;
    for (int i = 0; i < arr.Length; i++)
     if (Math.Abs(arr[i] - val) < Math.Abs(arr[index] - val))
      index = i;
    return arr[index];
}
Al W
Instead of computing `Math.Abs(arr[index] - val))` every time through the loop you should pull it out into a variable.
Allain Lalonde
I think you need a '<' instead if '=', in your loop.
Adeel Ansari
ok, ok, you got me...i typed it up in notepad.
Al W
+3  A: 

Assuming that the values start in a table called T with a column called N, and we are looking for the value 4 then in Oracle SQL it takes 59 characters:

select*from(select*from t order by abs(n-4))where rownum=1

I've used select * to reduce the whitespace requirements.

WW
is there no "select top 1 * from t order by abs(n-4)" type syntax in Oracle?
Jimmy
@Jimmy: Afraid not. Have to use the stupid rownum hack or analytics. Maybe a shorter version of this using analytics actually
WW
+5  A: 

My attempt in python:

def closest(target, collection) :
    return min((abs(target - i), i) for i in collection)[1]
sykora
A: 
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);
Michael Buen
A: 

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.

cletus
You can ditch this, can't you: if (haystack.length > 1)
WW
Yeah I can actually.
cletus
+1  A: 

Haskell entry (tested):

import Data.List

near4 = head . sortBy (\n1 n2 -> abs (n1-4) `compare` abs (n2-4))

Sorts the list by putting numbers closer to 4 near the the front. head takes the first element (closest to 4).

Norman Ramsey
+1  A: 

Ruby

def c(r,t)
r.sort{|a,b|(a-t).abs<=>(b-t).abs}[0]
end

Not the most efficient method, but pretty short.

Joshua Swink
+1  A: 

returns only one number:

var arr = new int[] { 1, 3, 8, 10, 13 };
int numToMatch = 4;
Console.WriteLine("{0}", 
     arr.Select(n => new{n, diff = Math.Abs(numToMatch - n) }).OrderBy(x => x.diff).ElementAt(0).n);
Michael Buen
+1  A: 

PostgreSQL:

select n from tbl order by abs(4 - n) limit 1
Michael Buen
+1  A: 

returns only one number:

var arr = new int[] { 1, 3, 8, 10, 13 };
int numToMatch = 4;

Console.WriteLine("{0}", 
   arr.OrderBy(n => Math.Abs(numToMatch - n)).ElementAt(0));
Michael Buen
+2  A: 

Groovy 28B

f={a,n->a.min{(it-n).abs()}}
matyr
+3  A: 

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

Andrew Backer
A: 

Common Lisp using iterate library.

(defun closest-match (list n)
     (iter (for i in list)
            (finding i minimizing (abs (- i n)))
+1  A: 

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));
}
strager
I like this one since unlike many of the others it does not involve a sort. It is just O(n)
ScottD
A: 

Perl -- 66 chars:

perl -e 'for(qw/1 3 8 10 13/){$d=($_-4)**2; $c=$_ if not $x or $d<$x;$x=$d;}print $c;'
gpojd
+15  A: 

11 bytes in J:

C=:0{]/:|@-

Examples:

>> a =: 1 3 8 10 13
>> 4 C a
3
>> 11 C a
10
>> 12 C a
13

my breakdown for the layman:

0{         First element of
]          the right argument
/:         sorted by
|          absolute value 
@          of
-          subtraction
Jimmy
down to 11 bytes now... that explicit @-chain and parentheses was bothering me.
Jimmy
A: 

Scala (62 chars), based on the idea of the J and Ruby solutions:

def c(l:List[Int],n:Int)=l.sort((a,b)=>(a-n).abs<(b-n).abs)(0)

Usage:

println(c(List(1,3,8,10,13),4))
Fabian Steeg
+5  A: 

Shorter Python: 41 chars

f=lambda a,l:min(l,key=lambda x:abs(x-a))
Triptych
+1  A: 

Because I actually needed to do this, here is my PHP

$match = 33;

$set = array(1,2,3,5,8,13,21,34,55,89,144,233,377,610);

foreach ($set as $fib)
    {
     $diff[$fib] = (int) abs($match - $fib);
    }
$fibs = array_flip($diff);
$closest = $fibs[min($diff)];

echo $closest;
garrow
A: 

41 characters in F#:

let C x = Seq.min_by (fun n -> abs(n-x))

as in

#light

let l = [1;3;8;10;13]

let C x = Seq.min_by (fun n -> abs(n-x))

printfn "%d" (C 4 l)   // 3 
printfn "%d" (C 11 l)  // 10
printfn "%d" (C 12 l)  // 13
Brian
Actually, you can make it even shorter - let C x = Seq.minBy (abs<<((-)x)) ... or let C x = Seq.minBy (((-)x)>>abs) ... whichever you prefer. :)
Matajon
A: 

Ruby like Python has a min method for Enumerable so you don't need to do a sort.

def c(value, t_array)
  t_array.min{|a,b|  (value-a).abs <=> (value-b).abs }
end

ar = [1, 3, 8, 10, 13]
t = 4
c(t) = 3
ScottD
A: 

Ruby. One pass-through. Handles negative numbers nicely. Perhaps not very short, but certainly pretty.

class Array
  def closest int
    diff = int-self[0]; best = self[0]
    each {|i|
      if (int-i).abs < diff.abs
        best = i; diff = int-i
      end
    }
    best
  end
end

puts [1,3,8,10,13].closest 4
nilamo
+1  A: 

Here's another Haskell answer:

import Control.Arrow
near4 = snd . minimum . map (abs . subtract 4 &&& id)
BONUS
Why waste characters with "import Control.Arrow" when you can go with standard Prelude's functions - map (\x -> (abs (x-4), x)).
Matajon
A: 

Haskell, 60 characters -

f a=head.Data.List.sortBy(compare`Data.Function.on`abs.(a-))
Matajon
+1  A: 

Kdb+, 23B:

C:{x first iasc abs x-}

Usage:

q)a:10?20
q)a
12 8 10 1 9 11 5 6 1 5

q)C[a]4
5
earl
A: 

Excel VBA - find Excel Range's Index or Value Closest to Target Value

Given an existing Excel Range, rangeOfValues:

1) find index of the closest matching value in the Range using Application.Match (note that the Match method returns a Double)

Dim iMatch as Double 
iMatch = Application.Match(valueToMatch, rangeOfValues)

2) find the closest Range value to the Target Value using VLOOKUP/HLOOKUP

Dim closest as Variant
closest = VLOOKUP(valueToMatch, rangeOfValues)

If an exact match is needed:

Dim exactM as Variant
exactM = VLOOKUP(valueToMatch, rangeOfValues, False)
RichC
A: 
Ren
A: 

another PHP answer:

function closestMatch($int, $in) {
    $diffs = array();
    foreach ($in as $i)
        $diffs[abs($int - $i)] = $i;
    ksort($diffs);
    foreach ($diffs as $i) return $i;
}
kbjr