Python X-ось ближайшая точка

Question

Я пытаюсь придумать простой алгоритм без импорта модулей, где у вас есть несколько точек х-оси, как

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

и где предложит пользователю ввести определенную точку, программа должна дать самую близкую точку к введенному значению пользователем, так как есть отрицательные значения, которые могут быть самыми близкими, мне просто нужна общая идея.

Answer 1

Два шаг:

1. Используйте bisect module найти индекс для ближайшего меньшего значения
2. Используйте абсолютное расстояние между этим ближайшим меньшим значением, а следующим, более высоким значением, чтобы выбрать один из этих двух.

Это алгоритм O (logN); для N точек должно выполняться не более log N шагов. Сравните это с сортировкой по абсолютному расстоянию, которое берет O (NlogN), чтобы найти ближайшую точку, или используя min(), беря O (N).

не принимать во внимание, что шаг можно выбрать индекс в начале или в конце, где нет ниже или выше второй пункт:

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

Демонстрация:

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

Для полноты, min() подход:

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

Answer 2

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

Что делает вышеприведенный код, возвращает минимальное значение абсолютного значения каждой точки и вычитает из него точку ввода пользователя.