CODEWITHSUNDEEP
pythonalgorithmpython-3.x
aero
aero

Reputation: 270

Python X-axis nearest point

I am trying to come up with a simple algorithm without importing modules where you have several x-axis points like

d = [-5, -3.5, -2.8, -0.6, 1.2, 3.4, 5.6]

and where you prompt the user to enter a certain point, the program should give the closest point to the entered value by the user,since there are negative values which can possibly be closest I just need a general idea.

Upvotes: 0

Views: 806

Answers (2)

Martijn Pieters
Martijn Pieters

Reputation: 1123640

Two steps:

  1. Use the bisect module to find the index for the nearest lower value
  2. Use the absolute distance between that nearest lower value and the next, higher value to pick one of those two.

This is a O(logN) algorithm; for N points at most log N steps have to be executed. Compare that to sorting by absolute distance, which takes O(NlogN) to find the nearest point, or using min() taking O(N).

Take into account that step one can pick an index at the start or end, where there is no lower or higher second point:

import bisect

def nearest(x, d):
    index = bisect.bisect(d, x)
    if not index:
        return d[index]  # left-most x coordinate
    if index == len(d):
        return d[-1]  # right-most x coordinate
    return min(d[index - 1:index + 1], key=lambda v: abs(v - x))

Demo:

>>> import bisect
>>> def nearest(x, d):
...     index = bisect.bisect(d, x)
...     if not index:
...         return d[index]  # left-most x coordinate
...     if index == len(d):
...         return d[-1]  # right-most x coordinate
...     return min(d[index - 1:index + 1], key=lambda v: abs(v - x))
... 
>>> d = [-5, -3.5, -2.8, -0.6, 1.2, 3.4, 5.6]
>>> nearest(10, d)
5.6
>>> nearest(-10, d)
-5
>>> nearest(0, d)
-0.6
>>> nearest(3, d)
3.4

For completeness sake, the min() approach is:

min(d, key=lambda v: abs(v - x))

Upvotes: 2

Beta Decay
Beta Decay

Reputation: 805

min(array, key=lambda x: abs(x)-point)

What the above code does is returns the minimum value of the absolute value of each point and subtracting the user input point from it.

Upvotes: 0

Related Questions