¿Cómo buscar el valor más cercano en una tabla de búsqueda?

Question

Tengo una única serie de valores enteros de dimmensional que representan un conjunto físico de valores de parte con los que tengo que trabajar. Luego calculo el valor ideal matemáticamente.

¿Cómo podría escribir un algoritmo de búsqueda eficiente que encuentre la diferencia de abosulte más pequeña de mi valor ideal en la matriz?

La matriz es predeterminada y constante, por lo que se puede ordenar como yo lo necesite. array

Ejemplo Lookup:

100, 152, 256, 282, 300 

La búsqueda de un valor ideal de 125 encontraría 100 en la matriz, mientras que 127 sería encontrar 152.

La matriz de búsqueda actual será de unos 250 artículos largo y nunca cambies

Answer 1

Una vez que se ordena matriz, utilice binary search

Answer 2

El simple hecho de pasar por la matriz y calcular abs (reference-array_value [i]) tomaría O (N). llevan el índice con la menor diferencia.

Answer 3

Python, la fuerza bruta en la lista sin ordenar (porque es divertido Python escrito) 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())] 

Y una correcta aplicación que utiliza la búsqueda binaria para encontrar el valor 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

Esto es muy similar a una búsqueda binaria, excepto si no encuentra la clave exacta, sería r una tecla debe estar muy cerca de la clave provista.

La lógica es buscar hasta que se encuentre la clave exacta o hasta que exista exactamente una tecla entre la tecla alta y la baja mientras se realiza la búsqueda binaria.

considerar una matriz n [] = {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
si la búsqueda de la clave: 2, a continuación, mediante el siguiente algoritmo
Paso 1: alto = 10, bajo = 0, med = 5
Paso 2: alto = 5, bajo = 0, med = 2
Paso 3: alto = 2, bajo = 0, med = 1 En este paso se encuentra la clave exacta. Por lo tanto, devuelve 1.

si la búsqueda de la clave: 3 (que no está presente en la matriz), a continuación, mediante el siguiente algoritmo
Paso 1: alta = 10, B = 0, med = 5
Paso 2: alto = 5, bajo = 0, med = 2
Paso 3: alto = 2, bajo = 0, med = 1
Paso 4: alto = 1, bajo = 0, en este paso alto = bajo + 1 es decir, no hay más elementos para buscar. Entonces devuelve med = 1.

Espero que esto ayude ...

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

El binario algoritmo de búsqueda de Wikipedia es la siguiente:

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

La condición final en caso de que no se encuentra una clave es que imax < imin.

De hecho, esta condición puede ubicar la coincidencia más cercana. La coincidencia más cercana se encontrará entre imax y imin (teniendo en cuenta que podría estar fuera de los límites de la matriz). Tenga en cuenta nuevamente que imax < imin en el caso final. Algunas soluciones utilizan abdominales para encontrar la diferencia, pero sabemos que por lo 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