Как искать самое близкое значение в справочной таблице?
У меня есть простой размерный массив целочисленных значений, которые представляют физическое множество значений части, с которыми я должен работать. Я затем вычисляю и идеальное значение математически.
Как я мог записать эффективный алгоритм поиска, который найдет самое маленькое abosulte различие от моего идеального значения в массиве?
Массив предопределяется и постоянный, таким образом, он может быть отсортирован однако, мне нужно.
Массив Поиска в качестве примера:
100, 152, 256, 282, 300
Поиск идеального значения 125 нашел бы 100 в массиве, тогда как 127 найдет 152.
Фактический массив поиска будет приблизительно 250 объектами долго и никогда не изменяться.
3 ответа
Python, грубая сила на несортированном списке (потому что писать на Python весело) O(n):
table = (100, 152, 256, 282, 300)
value = 125
lookup_dict = dict([(abs(value-x),x) for x in table])
closest_val = ldict[min(ldict.keys())]
И правильная реализация, использующая двоичный поиск для нахождения значения O(log_n):
import bisect
'''Returns the closest entry in the sorted list 'sorted' to 'value'
'''
def find_closest(sorted, value):
if (value <= sorted[0]):
return sorted[0]
if (value >= sorted[-1]):
return sorted[-1]
insertpos = bisect.bisect(sorted, value)
if (abs(sorted[insertpos-1] - value) <= abs(sorted[insertpos] - value)):
return sorted[insertpos-1]
else:
return sorted[insertpos]
Просто пройдя через массив и вычислив abs(reference-array_value[i]) потребуется O(N). нести индекс с наименьшей разницей.