Comparing the difference of integers in a list with a given value

Question

My Python is a bit rusty and I'm really having trouble with this super simple algorithm.

I'm trying to write a function that takes two parameters (target, values) to find which number in the values is closest to the target number; if there happens to be a tie, then select the lower number.

Here's my progress, but I've only ever selected the lower number without actually comparing the difference of the values in the list in comparison to the relative distance of the target.

So, in essence, my function hasn't actually completed the challenge correctly at all because 47 is actually closer to 46 than 31 is; however, if the numbers contained in the list were hypothetically 45 and 47, then they would be equally distant from my target number and so 45 should be printed and not 47.

I'd prefer answers that use simple for/if/while loops so that I can really practice my skills.

Other more advanced answers are also welcome with a detailed explanation.

EDIT

A few really good answers from you guys, much appreciated; I'm testing them as we speak and will choose the one most fitting to my style and use the rest as references, even if you have the best one-liner answer.

target = 46
values = [1, 22, 31, 47, 87, 99]

def closest_to_target(target, values):

    lower = []

    for number in values:
        if number < target:
            lower.append(number)

    if lower:
        lowest = sorted(lower, reverse=True)[0]
        return lowest

    else:
        return "Error handling array"


print closest_to_target(target, values)

Answer 1

You are only selecting numbers that are lesser than the target, irrespective of the difference. For a basic code example as you requested, you want to consider a modification on the linear search, but just keep track of the lowest difference and the value that produces this lowest difference.

    def closest(target, values):
        smallest_difference = #a really large value to start
        closest_number = None
        for number in values:
            diff = abs(number - target)
            if diff == smallest_difference and number < closest_number:
               closest_number = number
            if diff < smallest_difference:
               closest_number = number
               smallest_difference = diff
        return closest_number

The advantage of this method is that you don't create additional lists.

Answer 2

You can use the following function which creates tuples of values, and how close the value is to the target value. By sorting by this tuple, you not only get the element closest to the target value, but in the case of ties, will pick the smallest of the tied values.

target = 46
values = [1, 22, 31, 47, 87, 99]

def closest_min(l, t):
  return sorted([(abs(t-i), l[e]) for e, i in enumerate(l)])[0][1]

print(closest_min(values, target))

Output:

47

In the case of a tie, will correctly choose the lowest:

>>> closest_min([47, 45], 46)
45

A slightly neater version using min():

def closest_min(l, t):
      return min(l, key=lambda x:(abs(x-t), x))

Answer 3

This can be done in a single pass, keeping track of the deltas. If the delta is equal to the previous delta, the closest is the min of the previous closest and the current. If the delta is less, then update both the delta and the closest with the current values. Anything else, keep on going.

>>> target = 46
>>> values = [1, 22, 31, 47, 87, 99]
>>> closest = values[0]
>>> delta = abs(target - closest)
>>> for x in values:
...     d = abs(target - x)
...     if d == delta:
...         closest = min(closest, x)
...     elif d < delta:
...         delta = d
...         closest = x
...
>>> delta
1
>>> closest
47
>>>

Answer 4

def min_dist_index(target, values):
    values = sorted(values)
    dists = [abs(target-value) for value in values]
    index = dists.index(min(dists))
    return values[index]

target = 46
values = [1, 22, 31, 47, 87, 99]
print(min_dist_index(target, values))

Output: 47

Answer 5

You could generate a list of valid numbers which then could be processed with a so called list comprehension:

values[[abs(target-i) for i in values].index(min([abs(target-i) for i in values]))]

Here the list literal [] is used to define a generic algorithm instead of specific values what the contents of the list should be. Each element in the list, i, are derived from the list literal containing your values and are checked against the target number. If they do not qualify they are not contained within the new generated list.

Implementation:

#!/usr/bin/env python

target = 46
values = [1, 22, 31, 47, 87, 99]


def closest_to_target(target, values):
    lower = values[[abs(46-i) for i in values].index(min([abs(46-i) for i in values]))]
    return lower

print(closest_to_target(target, values))

Which will print:

47