如何在查找表中搜索最接近的值？

Question

我有一个简单的一维整数值数组，代表我必须使用的一组物理物理值。然后我用数学计算和理想值。

我该如何编写一个高效的搜索算法，以便在数组中找到与我理想值最小的差异？

该数组是预先确定的和常量，所以它可以按我需要排序。

例 查找阵列：

100, 152, 256, 282, 300 

在搜索125的理想值会在阵列中找到100，而127会发现152

实际查找阵列将是约250项长并永不改变。

Answer 1

一旦数组进行排序，使用binary search

Answer 2

只要通过数组并计算abs（reference-array_value [i]）就需要O（N）。 携带最小差异的指数。

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

Answer 4

这是非常相似的，除非它没有找到确切的关键二进制搜索，它会[R编辑一个密钥将非常接近所提供的密钥。

逻辑搜索直到找到确切的关键字，或者在执行二进制搜索时在高位键和低位之间只剩下一个关键字。

考虑一个数组n [] = {1，2，4，6，8，10，12，14，16，18，20}
如果搜索关键：2，然后使用以下算法步骤3：high = 2，low = 0，med = 1步骤1：高= 10，低= 0，med = 5在该步骤中，找到确切的关键。所以它返回1

如果搜索关键：3（其不存在阵列中），然后使用以下算法
步骤1：高= 10，低= 0，中值= 5
步骤2：高= 5，低= 0，中等= 2
步骤3：高= 2，低= 0，中等= 1
步骤4：高= 1，低= 0， 1即没有更多元素要搜索。所以它返回med = 1。

希望这有助于...

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

Answer 5

维基百科二进制搜索算法是如下：

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

的情况下的密钥未发现的结束条件是，imax < imin。

事实上，这种情况可以找到最近的匹配。最接近的匹配位于imax和imin之间（考虑到可能不在数组边界之外）。在最后的情况下再次注意imax < imin。一些解决方案采用ABS找到差异，但我们知道，A[imax] < key < A[imin]这样：

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