búsqueda de dedo
En informática , una búsqueda de dedo en una estructura de datos es una extensión de cualquier operación de búsqueda que admita la estructura, donde se proporciona una referencia (dedo) a un elemento en la estructura de datos junto con la consulta. Mientras que el tiempo de búsqueda de un elemento se expresa con mayor frecuencia en función del número de elementos en una estructura de datos, los tiempos de búsqueda de los dedos son una función de la distancia entre el elemento y el dedo.
En un conjunto de n elementos, la distancia d ( x , y ) (o simplemente d cuando no es ambiguo) entre dos elementos x e y es su diferencia de rango. Si x e y son los elementos i -ésimo y j -ésimo más grandes de la estructura, entonces la diferencia de rango es | yo - j |. Si una búsqueda normal en alguna estructura normalmente tomaría un tiempo O(f( n )), entonces una búsqueda de x con el dedo y idealmente debería tomar un tiempo O(f( d )). Comentar que desded ≤ n , se deduce que, en el peor de los casos, la búsqueda con el dedo es tan mala como la búsqueda normal. Sin embargo, en la práctica, estas búsquedas dactilares degeneradas funcionan más que las búsquedas normales. Por ejemplo, si f( n ) es log( n ), y la búsqueda con el dedo hace el doble de comparaciones que la búsqueda normal en el peor de los casos, se deduce que la búsqueda con el dedo es más lenta cuando d > √ n . Por lo tanto, la búsqueda con el dedo solo debe usarse cuando se puede esperar razonablemente que el objetivo esté realmente cerca del dedo.
Algunas estructuras de datos populares admiten la búsqueda con los dedos sin cambios adicionales en la estructura real. En las estructuras en las que la búsqueda de un elemento x se logra al reducir un intervalo en el que se puede encontrar x , la búsqueda con el dedo desde y generalmente se logra invirtiendo el proceso de búsqueda desde y hasta que el intervalo de búsqueda sea lo suficientemente grande como para contener x , en cuyo punto la búsqueda continúa con normalidad.
En una lista enlazada , normalmente se busca linealmente un elemento caminando de un extremo al otro. Si la lista enlazada está ordenada y tenemos una referencia a algún nodo que contiene y , entonces podemos encontrar x en el tiempo O( d ) al comenzar nuestra búsqueda desde y .
En una matriz ordenada A , normalmente se busca un elemento x en A con una búsqueda binaria . La búsqueda con los dedos se logra realizando una búsqueda unilateral desde A [ j ] = y . Mientras que la búsqueda binaria reduce a la mitad el espacio de búsqueda después de cada comparación, la búsqueda unilateral duplica el espacio de búsqueda después de cada comparación. Específicamente, en la k -ésima iteración de la búsqueda unilateral (suponiendo que x > y ), el intervalo bajo consideración es A [ j , j +2 k -1 ]. La expansión se detiene tan pronto comoA [ j + 2 k -1 ] ≥ x , en cuyo punto este intervalo se busca binariamente para x .
Si la búsqueda unilateral toma k iteraciones para encontrar un intervalo que contiene x , entonces se sigue que d > 2 k - 2 . La búsqueda binaria en este rango también requerirá otras k iteraciones. Por lo tanto, la búsqueda digital de x desde y requiere un tiempo O( k ) = O(log d ).
