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

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