如何在查阅表格中搜索最近的值?

数组排序后,使用 binary search

这与二进制搜索非常相似,除非它找不到确切的密钥,否则它将返回一个非常接近提供的密钥的密钥。

逻辑是在执行二进制搜索时,搜索直到找到精确的键,或者直到在高键和低键之间只剩下一个键。

考虑数组n[]=1、2、4、6、8、10、12、14、16、18、20
如果搜索键:2,则使用以下算法
步骤1:高=10,低=0,中=5
步骤2:高=5,低=0,中=2
第3步:高=2,低=0,中=1。在此步骤中,找到精确的键。所以它返回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);
                }
            }

维基百科的二进制搜索算法如下:

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 在最终情况下。有些解决方案使用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

只需遍历数组并计算abs(引用数组_值[i])就可以得到o(n)。 以最小的差异携带索引。

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]