Get the closest number out of an array

Question

I have a number from minus 1000 to plus 1000 and I have an array with numbers in it  Like this    2  42  82  122  162  202  242  282  322  362    I want that the number I ve got changes to the nearest number of the array   For example I get 80 as number I want it to get 82

User · Answer

include  lt algorithm gt   include  lt iostream gt   include  lt cmath gt   using namespace std   class CompareFunctor    public      CompareFunctor int n     n   n        bool operator   int  amp  val1  int  amp  val2                int diff1   abs val1 -  n           int diff2   abs val2 -  n           return  diff1  lt  diff2          private      int  n      int Find Closest Value int nums    int size  int n        CompareFunctor cf n       int cn    min element nums  nums   size  cf       return cn     int main         int nums       2  42  82  122  162  202  242  282  322  362        int size   sizeof nums    sizeof int       int n   80      int cn   Find Closest Value nums  size  n       cout  lt  lt    nClosest value      lt  lt  cn  lt  lt  endl      cin get

User · Answer

All of the solutions are over-engineered  It is as simple as  const needle   5  const haystack    1  2  3  4  5  6  7  8  9    haystack sort  a  b    gt      return Math abs a - needle  - Math abs b - needle      0       5

User · Answer

Here s the pseudo-code which should be convertible into any procedural language   array    2  42  82  122  162  202  242  282  322  362  number   112 print closest  number  array   def closest  num  arr       curr   arr 0      foreach val in arr          if abs  num - val   lt  abs  num - curr               curr   val     return curr   It simply works out the absolute differences between the given number and each array element and gives you back one of the ones with the minimal difference   For the example values   number   112  112  112  112  112  112  112  112  112  112 array      2   42   82  122  162  202  242  282  322  362 diff     110   70   30   10   50   90  130  170  210  250                                                      -- one with minimal absolute difference    As a proof of concept  here s the Python code I used to show this in action   def closest  num  arr       curr   arr 0      for index in range  len  arr            if abs  num - arr index    lt  abs  num - curr               curr   arr index      return curr  array    2  42  82  122  162  202  242  282  322  362  number   112 print closest  number  array      And  if you really need it in Javascript  see below for a complete HTML file which demonstrates the function in action    lt html gt       lt head gt  lt  head gt       lt body gt           lt script language  javascript  gt              function closest  num  arr                    var curr   arr 0                   var diff   Math abs  num - curr                   for  var val   0  val  lt  arr length  val                          var newdiff   Math abs  num - arr val                        if  newdiff  lt  diff                            diff   newdiff                          curr   arr val                                                           return curr                            array    2  42  82  122  162  202  242  282  322  362               number   112              alert  closest  number  array             lt  script gt       lt  body gt   lt  html gt      Now keep in mind there may be scope for improved efficiency if  for example  your data items are sorted  that could be inferred from the sample data but you don t explicitly state it   You could  for example  use a binary search to find the closest item   You should also keep in mind that  unless you need to do it many times per second  the efficiency improvements will be mostly unnoticable unless your data sets get much larger   If you do want to try it that way  and can guarantee the array is sorted in ascending order   this is a good starting point    lt html gt       lt head gt  lt  head gt       lt body gt           lt script language  javascript  gt              function closest  num  arr                    var mid                  var lo   0                  var hi   arr length - 1                  while  hi - lo  gt  1                        mid   Math floor   lo   hi    2                       if  arr mid   lt  num                            lo   mid                        else                           hi   mid                                                          if  num - arr lo   lt   arr hi  - num                        return arr lo                                     return arr hi                             array    2  42  82  122  162  202  242  282  322  362               number   112              alert  closest  number  array             lt  script gt       lt  body gt   lt  html gt    It basically uses bracketing and checking of the middle value to reduce the solution space by half for each iteration  a classic O log N  algorithm whereas the sequential search above was O N    0  1  2   3   4   5   6   7   8   9   lt - indexes 2 42 82 122 162 202 242 282 322 362   lt - values L             M                   H  L 0  H 9  M 4  162 higher  H lt -M L     M       H                      L 0  H 4  M 2  82 lower equal  L lt -M       L   M   H                      L 2  H 4  M 3  122 higher  H lt -M       L   H                          L 2  H 3  difference of 1 so exit                                   H  122-112 10  is closer than L  112-82 30  so choose H   As stated  that shouldn t make much of a difference for small datasets or for things that don t need to be blindingly fast  but it s an option you may want to consider

User · Answer

This solution uses ES5 existential quantifier Array some  which allows to stop the iteration  if a condition is met   Opposit of Array reduce  it does not need to iterate all elements for one result   Inside the callback  an absolute delta between the searched value and actual item is taken and compared with the last delta  If greater or equal  the iteration stops  because all other values with their deltas are greater than the actual value   If the delta in the callback is smaller  then the actual item is assigned to the result and the delta is saved in lastDelta   Finally  smaller values with equal deltas are taken  like in the below example of 22  which results in 2   If there is a priority of greater values  the delta check has to be changed from   if  delta  gt   lastDelta      to   if  delta  gt  lastDelta                 without equal sign   This would get with 22  the result 42  Priority of greater values    This function needs sorted values in the array     Code with priority of smaller values    x000D   x000D  function closestValue array  value    x000D      var result  x000D          lastDelta  x000D   x000D      array some function  item    x000D          var delta   Math abs value - item   x000D          if  delta  gt   lastDelta    x000D              return true  x000D            x000D          result   item  x000D          lastDelta   delta  x000D          x000D      return result  x000D    x000D   x000D  var data    2  42  82  122  162  202  242  282  322  362   x000D   x000D  console log 21  closestValue data  21       2 x000D  console log 22  closestValue data  22       2  smaller value x000D  console log 23  closestValue data  23       42 x000D  console log 80  closestValue data  80       82 x000D   x000D   x000D    Code with priority of greater values    x000D   x000D  function closestValue array  value    x000D      var result  x000D          lastDelta  x000D   x000D      array some function  item    x000D          var delta   Math abs value - item   x000D          if  delta  gt  lastDelta    x000D              return true  x000D            x000D          result   item  x000D          lastDelta   delta  x000D          x000D      return result  x000D    x000D   x000D  var data    2  42  82  122  162  202  242  282  322  362   x000D   x000D  console log 21  closestValue data  21        2 x000D  console log 22  closestValue data  22       42 greater value x000D  console log 23  closestValue data  23       42 x000D  console log 80  closestValue data  80       82 x000D   x000D   x000D

User · Answer

ES6 Works with sorted and unsorted arrays Numbers Integers and Floats  Strings welcomed        Finds the nearest value in an array of numbers     Example  nearestValue array  42          param  Array lt number gt   arr     param  number  val the ideal value for which the nearest or equal should be found     const nearestValue    arr  val    gt  arr reduce  p  n    gt   Math abs p   gt  Math abs n - val    n - val   p   Infinity    val   Examples  let values    1 2 3 4 5  console log nearestValue values  10      -- gt  5 console log nearestValue values  0      -- gt  1 console log nearestValue values  2 5      -- gt  2  values    100 5 90 56  console log nearestValue values  42      -- gt  56  values     100   5   90   56   console log nearestValue values  42      -- gt  56

User · Answer

I don t know if I m supposed to answer an old question  but as this post appears first on Google searches  I hoped that you would forgive me adding my solution  amp  my 2c here   Being lazy  I couldn t believe that the solution for this question would be a LOOP  so I searched a bit more and came back with filter function   var myArray    2  42  82  122  162  202  242  282  322  362   var myValue   80   function BiggerThan inArray      return inArray  gt  myValue     var arrBiggerElements   myArray filter BiggerThan   var nextElement   Math min apply null  arrBiggerElements   alert nextElement     That s all

User · Answer

The most efficient would be a binary search  However even simple solutions can exit when the next number is a further match from the current  Nearly all solutions here are not taking into account that the array is ordered and iterating though the whole thing      x000D   x000D  const closest    orderedArray  value  valueGetter   item   gt  item    gt  x000D    orderedArray find  item  i    gt  x000D      i     orderedArray length - 1    x000D      Math abs value - valueGetter item    lt  Math abs value - valueGetter orderedArray i   1      x000D   x000D  var data    2  42  82  122  162  202  242  282  322  362   x000D   x000D  console log  21 - gt  2   closest data  21      2   x000D  console log  22 - gt  42   closest data  22      42      equidistant between 2 and 42  select highest x000D  console log  23 - gt  42   closest data  23      42   x000D  console log  80 - gt  82   closest data  80      82   x000D   x000D   x000D    This can be run on non-primitives too e g  closest data  21  item   gt  item age   Change find to findIndex to return the index in the array

User · Answer

Another variant here we have circular range connecting head to toe and accepts only min value to given input  This had helped me get char code values for one of the encryption algorithm   function closestNumberInCircularRange codes  charCode      return codes reduce  p code  c code   gt       if   Math abs p code-charCode   gt  Math abs c code-charCode      p code  gt  charCode   amp  amp  c code  lt  charCode         return c code       else if p code  lt  charCode         return p code       else if p code  gt  charCode  amp  amp  c code  gt  charCode         return Math max apply Math   p code  c code              return p code

User · Answer

Works with unsorted arrays  While there were some good solutions posted here  JavaScript is a flexible language that gives us tools to solve a problem in many different ways  It all comes down to your style  of course  If your code is more functional  you ll find the reduce variation suitable  i e      arr reduce function  prev  curr        return  Math abs curr - goal   lt  Math abs prev - goal    curr   prev           However  some might find that hard to read  depending on their coding style  Therefore I propose a new way of solving the problem     var findClosest   function  x  arr        var indexArr   arr map function k    return Math abs k - x         var min   Math min apply Math  indexArr      return arr indexArr indexOf min          findClosest 80   2  42  82  122  162  202  242  282  322  362      Outputs 82   Contrary to other approaches finding the minimum value using Math min apply  this one doesn t require the input array arr to be sorted  We don t need to care about the indexes or sort it beforehand   I ll explain the code line by line for clarity    arr map function k    return Math abs k - x     Creates a new array  essentially storing the absolute values of the given numbers  number in arr  minus the input number  x   We ll look for the smallest number next  which is also the closest to the input number  Math min apply Math  indexArr  This is a legit way of finding the smallest number in the array we ve just created before  nothing more to it  arr indexArr indexOf min   This is perhaps the most interesting part  We have found our smallest number  but we re not sure if we should add or subtract the initial number  x   That s because we used Math abs   to find the difference  However  array map creates  logically  a map of the input array  keeping the indexes in the same place  Therefore  to find out the closest number we just return the index of the found minimum in the given array indexArr indexOf min     I ve created a bin demonstrating it

User · Answer

My answer to a similar question is accounting for ties too and it is in plain Javascript  although it doesn t use binary search so it is O N  and not O logN    var searchArray   0  30  60  90   var element  33   function findClosest array elem       var minDelta   null      var minIndex   null      for  var i   0   i lt array length  i             var delta   Math abs array i -elem           if  minDelta    null    delta  lt  minDelta               minDelta   delta              minIndex   i                      if it is a tie return an array of both values         else if  delta    minDelta                return  array minIndex  array i               if it has already found the closest value         else               return array i-1                        return array minIndex     var closest   findClosest searchArray element     https   stackoverflow com a 26429528 986160

User · Answer

I like the approach from Fusion  but there s a small error in it  Like that it is correct       function closest array  number            var num   0          for  var i   array length - 1  i  gt   0  i--                if Math abs number - array i    lt  Math abs number - array num                     num   i                                  return array num           It it also a bit faster because it uses the improved for loop   At the end I wrote my function like this       var getClosest   function number  array            var current   array 0           var difference   Math abs number - current           var index   array length          while  index--                var newDifference   Math abs number - array index                if  newDifference  lt  difference                    difference   newDifference                  current   array index                                   return current           I tested it with console time   and it is slightly faster than the other function

User · Answer

For a small range  the simplest thing is to have a map array  where  eg  the 80th entry would have the value 82 in it  to use your example   For a much larger  sparse range  probably the way to go is a binary search   With a query language you could query for values some distance either side of your input number and then sort through the resulting reduced list   But SQL doesn t have a good concept of  next  or  previous   to give you a  clean  solution

User · Answer

ES5 Version    x000D   x000D  var counts    4  9  15  6  2   x000D    goal   5  x000D   x000D  var closest   counts reduce function prev  curr    x000D    return  Math abs curr - goal   lt  Math abs prev - goal    curr   prev   x000D      x000D   x000D  console log closest   x000D   x000D   x000D

User · Answer

For sorted arrays  linear search   All answers so far concentrate on searching through the whole array  Considering your array is sorted already and you really only want the nearest number this is probably the fastest solution    x000D   x000D  var a    2  42  82  122  162  202  242  282  322  362   x000D  var target   90000  x000D   x000D      x000D     Returns the closest number from a sorted array  x000D       x000D  function closest arr  target    x000D    if    arr     arr length    0  x000D      return null  x000D    if  arr length    1  x000D      return arr 0   x000D   x000D    for  var i   1  i  lt  arr length  i      x000D         As soon as a number bigger than target is found  return the previous or current x000D         number depending on which has smaller difference to the target  x000D      if  arr i   gt  target    x000D        var p   arr i - 1   x000D        var c   arr i  x000D        return Math abs p - target   lt  Math abs c - target    p   c  x000D        x000D      x000D       No number in array is bigger so return the last  x000D    return arr arr length - 1   x000D    x000D   x000D     Trying it out x000D  console log closest a  target    x000D   x000D   x000D    Note that the algorithm can be vastly improved e g  using a binary tree

User · Answer

To Find Two Closest Number in array function findTwoClosest givenList  goal      var first    var second    var finalCollection    givenList 0   givenList 1      givenList forEach  item  firtIndex    gt        first   item       for  let i   firtIndex   1  i  lt  givenList length  i            second   givenList i          if  first   second  lt  goal            if  first   second  gt  finalCollection 0    finalCollection 1               finalCollection    first  second                                    return finalCollection     var counts    2  42  82  122  162  202  242  282  322  362  var goal   80  console log findTwoClosest counts  goal

User · Answer

ES6  ECMAScript 2015  Version   x000D   x000D  const counts    4  9  15  6  2   const goal   5   const output   counts reduce  prev  curr    gt  Math abs curr - goal   lt  Math abs prev - goal    curr   prev    console log output   x000D   x000D   x000D   For reusability you can wrap in a curry function that supports placeholders  http   ramdajs com 0 19 1 docs  curry or https   lodash com docs curry   This gives lots of flexibility depending on what you need   x000D   x000D  const getClosest     curry  counts  goal    gt      return counts reduce  prev  curr    gt  Math abs curr - goal   lt  Math abs prev - goal    curr   prev        const closestToFive   getClosest    5   const output   closestToFive  4  9  15  6  2     console log output   x000D   lt script src  https   cdn jsdelivr net npm lodash 4 17 20 lodash min js  gt  lt  script gt  x000D   x000D   x000D

User · Answer

Working code as below    x000D   x000D  var array    2  42  82  122  162  202  242  282  322  362   x000D   x000D  function closest array  num    x000D    var i   0  x000D    var minDiff   1000  x000D    var ans  x000D    for  i in array    x000D      var m   Math abs num - array i    x000D      if  m  lt  minDiff    x000D        minDiff   m  x000D        ans   array i   x000D        x000D      x000D    return ans  x000D    x000D  console log closest array  88    x000D   x000D   x000D

User · Answer

Here is the Code snippet to find the closest element to a number from an array in Complexity O nlog n    -  Input  -  1 60 0 -10 100 87 56  Element - 56 Closest Number in Array - 60  Source Code  Java    package com algo closestnumberinarray  import java util TreeMap    public class Find Closest Number In Array        public static void main String arsg              int array       1  60  0  -10  100  87  69            int number   56          int num   getClosestNumber array  number           System out println  Number is     num              public static int getClosestNumber int   array  int number            int diff     new int array length            TreeMap lt Integer  Integer gt  keyVal   new TreeMap lt Integer  Integer gt             for  int i   0  i  lt  array length  i                   if  array i   gt  number                    diff i    array i  - number                  keyVal put diff i   array i                  else                   diff i    number - array i                   keyVal put diff i   array i                                      int closestKey   keyVal firstKey            int closestVal   keyVal get closestKey            return closestVal

User · Answer

A slightly modified binary search on the array would work

User · Answer

A simpler way with O n  time complexity is to do this in one iteration of the array  This method is intended for unsorted arrays  Following is a javascript example  here from the array we find the number which is nearest to  quot 58 quot    x000D   x000D  var inputArr    150  5  200  50  30   var search   58  var min   Math min    var result   0  for i 0 i lt inputArr length i        let absVal   Math abs search - inputArr i     if min  gt  absVal        min absVal      result   inputArr i         console log result     expected output 50 if input is 58 x000D   x000D   x000D   This will work for positive  negative  decimal numbers as well  Math min   will return Infinity  The result will store the value nearest to the search element

[javascript] Get the closest number out of an array

Examples related to javascript

Examples related to arrays