How to search for closest value in a lookup table?

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.

---

Once array is sorted, use binary search

---

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

---

The binary search algorithm from Wikipedia is as below:

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imax >= imin)
    {
      // calculate the midpoint for roughly equal partition
      int imid = midpoint(imin, imax);
      if(A[imid] == key)
        // key found at index imid
        return imid; 
      // determine which subarray to search
      else if (A[imid] < key)
        // change min index to search upper subarray
        imin = imid + 1;
      else         
        // change max index to search lower subarray
        imax = imid - 1;
    }
  // key was not found
  return KEY_NOT_FOUND;
}

The end condition in case a key is not found is that imax < imin.

In fact, this condition can locate the nearest match. The nearest match will lie between imax and imin (taking into account either might be outside the array bounds). Note again that imax < imin in the end case. Some solutions use abs to find the difference, but we know that A[imax] < key < A[imin] so:

if imax <= 0 return 0
if imin >= A.count - 1 return A.count - 1
if (key - A[imax]) < (A[imin] - key) return imax
return imin

---

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]

---

Java has a Arrays.binarySearch function. Given an array of [10, 20, 30] you would get these results:

Search for	Result
10	0
20	1
30	2
7	-1
9	-1
11	-2
19	-2
21	-3
29	-3
43	-4

Sample code:

import java.util.Arrays;


public class Solution {
    public static void main(String[] args) {
        int[] array = new int[]{10, 20, 30};
        int[] keys = new int[]{10, 20, 30, 7, 9, 11, 19, 21, 29, 43};
        for (int key: keys) {
            System.out.println(Arrays.binarySearch(array, key));
        }
    }
}

Sample output:

1
2
-1
-1
-2
-2
-3
-3
-4

Basically the negative numbers provide 2 crucial information. Negative denotes that the exact match was not found but we can get a "close enough" match. The negative value indicates where the match is, -2 means: array[0] < key < array[1] and -3 means array[1] < key < array[2]. -1 means it is smaller than the minimum value in the array.

Example based on sample data on the initial question:

public class Solution {
    public static void main(String[] args) {
        int[] array = new int[]{100, 152, 256, 282, 300};
        int[] keys = new int[]{125, 127, 282, 4, 900, 126};
        for (int key : keys) {
            int index = Arrays.binarySearch(array, key);
            if (index >= 0) {
                System.out.println("Found " + key);
            } else {
                if (index == -1) {
                    //smaller than smallest in the array
                    System.out.println("Closest to " + key + " is " + array[0]);
                } else if (-index > array.length) {
                    //larger than the largest in the array
                    System.out.println("Closest to " + key + " is " + array[array.length - 1]);
                } else {
                    //in between
                    int before = array[0 - index - 2];
                    int after = array[0 - index - 1];
                    if (key - before < after - key) {
                        System.out.println("Closest to " + key + " is " + before);
                    } else if (key - before > after - key) {
                        System.out.println("Closest to " + key + " is " + after);
                    } else {
                        System.out.println("Same distance from " + key + " to " + before + " and " + after);
                    }
                }
            }
        }
    }
}

And the output:

Closest to 125 is 100
Closest to 127 is 152
Found 282
Closest to 4 is 100
Closest to 900 is 300
Same distance from 126 to 100 and 152

---

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