from list of integers get number closest to a given value

Question

Given a list of integers  I want to find which number is the closest to a number I give in input    gt  gt  gt  myList    4  1  88  44  3   gt  gt  gt  myNumber   5  gt  gt  gt  takeClosest myList  myNumber      4   Is there any quick way to do this

User · Answer

gt  gt  gt  takeClosest   lambda num collection min collection key lambda x abs x-num    gt  gt  gt  takeClosest 5  4 1 88 44 3   4   A lambda is a special way of writing an  anonymous  function  a function that doesn t have a name   You can assign it any name you want because a lambda is an expression   The  long  way of writing the the above would be   def takeClosest num collection      return min collection key lambda x abs x-num

User · Answer

It s important to note that Lauritz s suggestion idea of using bisect does not actually find the closest value in MyList to MyNumber  Instead  bisect finds the next value in order after MyNumber in MyList  So in OP s case you d actually get the position of 44 returned instead of the position of 4    gt  gt  gt  myList    1  3  4  44  88    gt  gt  gt  myNumber   5  gt  gt  gt  pos    bisect left myList  myNumber    gt  gt  gt  myList pos      44   To get the value that s closest to 5 you could try converting the list to an array and using argmin from numpy like so    gt  gt  gt  import numpy as np  gt  gt  gt  myNumber   5     gt  gt  gt  myList    1  3  4  44  88    gt  gt  gt  myArray   np array myList   gt  gt  gt  pos    np abs myArray-myNumber   argmin    gt  gt  gt  myArray pos      4   I don t know how fast this would be though  my guess would be  not very

User · Answer

Iterate over the list and compare the current closest number with abs currentNumber - myNumber    def takeClosest myList  myNumber       closest   myList 0      for i in range 1  len myList            if abs i - myNumber   lt  closest              closest   i     return closest

User · Answer

Expanding upon Gustavo Lima s answer  The same thing can be done without creating an entirely new list  The values in the list can be replaced with the differentials as the FOR loop progresses   def f ClosestVal v List  v Number      Takes an unsorted LIST of INTs and RETURNS INDEX of value closest to an INT    for  index  i in enumerate v List       v List  index    abs v Number - i  return v List index min v List           myList    1  88  44  4  4  -2  3  v Num   5 print f ClosestVal myList  v Num      Gives  3   the index of the first  4  in the list

User · Answer

If I may add to  Lauritz s answer  In order not to have a run error don t forget to add a condition before the bisect left line   if  myNumber  gt  myList -1  or myNumber  lt  myList 0        return False   so the full code will look like   from bisect import bisect left  def takeClosest myList  myNumber               Assumes myList is sorted  Returns closest value to myNumber      If two numbers are equally close  return the smallest number      If number is outside of min or max return False             if  myNumber  gt  myList -1  or myNumber  lt  myList 0            return False     pos   bisect left myList  myNumber      if pos    0              return myList 0      if pos    len myList               return myList -1      before   myList pos - 1      after   myList pos      if after - myNumber  lt  myNumber - before         return after     else         return before

User · Answer

def closest list  Number       aux          for valor in list          aux append abs Number-valor        return aux index min aux     This code will give you the index of the closest number of Number in the list   The solution given by KennyTM is the best overall  but in the cases you cannot use it  like brython   this function will do the work

User · Answer

I ll rename the function take closest to conform with PEP8 naming conventions   If you mean quick-to-execute as opposed to quick-to-write  min should not be your weapon of choice  except in one very narrow use case  The min solution needs to examine every number in the list and do a calculation for each number  Using bisect bisect left instead is almost always faster   The  almost  comes from the fact that bisect left requires the list to be sorted to work  Hopefully  your use case is such that you can sort the list once and then leave it alone  Even if not  as long as you don t need to sort before every time you call take closest  the bisect module will likely come out on top  If you re in doubt  try both and look at the real-world difference   from bisect import bisect left  def take closest myList  myNumber               Assumes myList is sorted  Returns closest value to myNumber       If two numbers are equally close  return the smallest number              pos   bisect left myList  myNumber      if pos    0          return myList 0      if pos    len myList           return myList -1      before   myList pos - 1      after   myList pos      if after - myNumber  lt  myNumber - before         return after     else         return before   Bisect works by repeatedly halving a list and finding out which half myNumber has to be in by looking at the middle value  This means it has a running time of O log n  as opposed to the O n  running time of the highest voted answer  If we compare the two methods and supply both with a sorted myList  these are the results      python -m timeit -s   from closest import take closest from random import randint a   range -1000  1000  10    take closest a  randint -1100  1100     100000 loops  best of 3  2 22 usec per loop    python -m timeit -s   from closest import with min from random import randint a   range -1000  1000  10    with min a  randint -1100  1100     10000 loops  best of 3  43 9 usec per loop   So in this particular test  bisect is almost 20 times faster  For longer lists  the difference will be greater   What if we level the playing field by removing the precondition that myList must be sorted  Let s say we sort a copy of the list every time take closest is called  while leaving the min solution unaltered  Using the 200-item list in the above test  the bisect solution is still the fastest  though only by about 30    This is a strange result  considering that the sorting step is O n log n    The only reason min is still losing is that the sorting is done in highly optimalized c code  while min has to plod along calling a lambda function for every item  As myList grows in size  the min solution will eventually be faster  Note that we had to stack everything in its favour for the min solution to win

User · Answer

If we are not sure that the list is sorted  we could use the built-in min   function  to find the element which has the minimum distance from the specified number    gt  gt  gt  min myList  key lambda x abs x-myNumber   4   Note that it also works with dicts with int keys  like  1   a   2   b    This method takes O n  time     If the list is already sorted  or you could pay the price of sorting the array once only  use the bisection method illustrated in  Lauritz s answer which only takes O log n  time  note however checking if a list is already sorted is O n  and sorting is O n log n

[python] from list of integers, get number closest to a given value

Examples related to python

Examples related to list

Examples related to sorting

Examples related to integer