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

Once array is sorted, use binary search

Answer 2

This is very similar to a binary search except if it does not find the exact key, it would return a key would be very close to the provided key.

Logic is to search till exact key is found or till there exactly one key left between high key and the low while performing binary search.

Consider an array n[] = {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
if you search for the key: 2, then using below algorithm
Step 1: high=10, low=0, med=5
Step 2: high=5, low=0, med=2
Step 3: high=2, low=0, med=1 In this step the exact key is found. So it returns 1.

if you search for the key:3 (which is not present in the array), then using below algorithm
Step 1: high=10, low=0, med=5
Step 2: high=5, low=0, med=2
Step 3: high=2, low=0, med=1
Step 4: high=1, low=0, At this step high=low+1 i.e. no more element to search. So it returns med=1.

Hope this helps...

public static <T> int binarySearch(List<T> list, T key, Comparator<T> compare) {
                int low, high, med, c;
                T temp;
                high = list.size();
                low = 0;
                med = (high + low) / 2;

                while (high != low+1) {
                    temp = list.get(med);
                    c = compare.compare(temp, key);

                    if (c == 0) {
                        return med;
                    } else if (c < 0){
                        low = med;
                    }else{
                        high = med;
                    }

                    med = (high + low) / 2;
                }

                return med; 
            }

    /** ------------------------ Example -------------------- **/

    public static void main(String[] args) {
                List<Integer> nos = new ArrayList<Integer>();
                nos.addAll(Arrays.asList(new Integer[]{1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}));

                search(nos, 2); // Output Search:2  Key:1   Value:2
                search(nos, 3); // Output Search:3  Key:1   Value:2

                search(nos, 10); // Output Search:10    Key:5   Value:10
                search(nos, 11); // Output Search:11    Key:5   Value:10
            }

    public static void search(List<Integer> nos, int search){
                int key = binarySearch(nos, search, new IntComparator());
                System.out.println("Search:"+search+"\tKey:"+key+"\tValue:"+nos.get(key));
            }

            public static class IntComparator implements Comparator<Integer>{
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1.compareTo(o2);
                }
            }