How to search for closest value in a lookup table?

Question

I have a simple one dimmensional array of integer values that represent a physical set of part values I have to work with. I then calculate and ideal value mathematically.

How could I write an efficient search algorithm that will find the smallest abosulte difference from my ideal value in the array?

The array is predetermined and constant, so it can be sorted however I need.

Example Lookup array:

100, 152, 256, 282, 300

Searching for an ideal value of 125 would find 100 in the array, whereas 127 would find 152.

The actual lookup array will be about 250 items long and never change.

Answer 1

Just going through the array and computing abs(reference-array_value[i]) would take O(N). carry the index with the smallest difference.

Answer 2

Once array is sorted, use binary search

Answer 3

Python, brute force on unsorted list (cause it's fun writing 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())]

And a proper implementation that uses binary search to find the value 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]