Métodos de búsqueda
Unidad 6
Búsqueda
• Operación importante en el procesamiento de la información
• Permite la recuperación de datos previamente almacenados.
• Se clasifica como interna o externa, según el lugar en el que esté
almacenada la información  en memoria o en dispositivos externos
• Finalidades:
- Determinar si el elemento buscado se encuentra en el conjunto en el
que se busca.
- Si el elemento está en el conjunto, hallar la posición en la que se
encuentra.
• Tipos:
– búsqueda secuencial,
– la binaria
– búsqueda utilizando tablas de hash.
Búsqueda secuencial
• Consiste en recorrer y examinar cada uno de los
elementos del arreglo hasta encontrar el o los
elementos buscados, o hasta que se han mirado
todos los elementos del arreglo.
• for(i=j=0;i<N;i++)
• if(arreglo[i]==elemento)
• {
•
solucion[j]=i;
•
j++;
• }
Búsqueda binaria o dicotómica
• el arreglo debe estar ordenado.
• La búsqueda binaria consiste en dividir el
arreglo por su elemento medio en dos
subarreglos más pequeños,
• comparar el elemento con el del centro. Si
coinciden, la búsqueda se termina.
• Si el elemento es menor, debe estar (si está)
en el primer subarreglo, y si es mayor está en
el segundo.
Ejemplo
• Para buscar el elemento 3 en el arreglo {1,2,3,4,5,6,7,8,9} se
realizarían los siguientes pasos:
• Se toma el elemento central y se divide el arreglo en dos:
• {1,2,3,4}-5-{6,7,8,9}
• Como el elemento buscado (3) es menor que el central (5), debe
estar en el primer subarreglo: {1,2,3,4}
• Se vuelve a dividir el arreglo en dos:
• {1}-2-{3,4}
• Como el elemento buscado es mayor que el central, debe estar en
el segundo subarreglo: {3,4}
• Se vuelve a dividir en dos:
• {}-3-{4}
• Como el elemento buscado coincide con el central, lo hemos
encontrado.
Búsqueda con tablas de hash
• Las tabla hash realizan la búsqueda e inserción
muy rápidamente.
• Se uso un arreglo.
• A cada dato se le asigna, mediante una
fórmula matemática denominada función
hash, una posición única en la tabla.
• Así la búsqueda, la inserción y el borrado son
inmediatos: O(1).
Desventajas
• ⇒ No se puede recorrer el contenido de una
tabla hash.
• ⇒ Como la posición de una palabra se calcula
de forma matemática, los datos no pueden
almacenarse ordenados.
• ⇒ Si permitimos datos duplicados se produce
lo que se denomina “colisión”, que consiste en
que a dos palabras se les asigna la misma
posición en el arreglo.
Función hash
• Proponemos como una primera función hash la
suma del código ASCII de cada una de las letras
de la palabra:
Palabra Last
F (Palabra) = Σ
Character Pos (Palabra (i)
i Palabra First
• Por ejemplo: F("alfredo") = 97 + 108 + 102 + 114
+ 101 + 100 + 111 = 733
Problemas con la función
• Colisión 1 : Palabras idénticas.
• Colisión 2 : Palabras formadas por las mismas
letras pero en distinto
• orden.
• Colisión 3 : Palabras distintas cuyas letras dan
la misma suma.
• La suma da números muy pequeños.
Otra función
• Para evitar que se produzcan resultados demasiado
elevados, dividimos el resultado de la función de la
solución anterior entre el tamaño de la tabla hash y
tomar como resultado de la nueva función hash el
resto de esta división.
• F(Palabra) = Polinomio(Palabra) mod Tamaño _Tabla
• Ejemplo:
•
F("alfredo") = (7.277 + 6.276 + 5.275 + 4.274 + 3.273 + 2.272
+1.271) mod 7
• Problemas:
– Se producen muchas colisiones debido a la reducción del
resultado de la función hash con el “mod”.
Solución al problema de las colisiones
• memoria dinámica: Cada posición de la tabla
hash contiene una lista o un árbol.
• De esta forma, si a dos palabras les
corresponde la misma posición de la tabla 
insertar ambas en la lista o en el árbol, según
sea el caso.
Otra solución
• Buscar, mediante saltos, otra posición de
inserción de la palabra a partir de la posición
que le corresponde según la función hash,
sólo en el caso de que esta posición esté
ocupada, es decir, sólo si se produce una
colisión.
Ejemplo:
• Salto = Posición + n, con n = 1, 2, ... De esta forma
insertaremos la nueva palabra en la posición no ocupada más
próxima a partir de la posición que le correspondería en
realidad.
Ejemplo (cont)
Observaciones
• Fijar el tamaño de la tabla hash como el doble del
necesario para almacenar todos los elementos.
– Ya que si queremos ampliar el tamaño de la tabla, como la
función hash depende del tamaño de ésta, hay que
recalcular las posiciones de todos los elementos e
insertarlos en estas nuevas posiciones (NO se puede copiar
directamente el contenido de una tabla a otra).
• El tamaño de la tabla debe ser un número primo para
evitar bucles infinitos.
• No permitir datos duplicados a no ser que vayamos a
implementar la tabla hash con listas,
– si se almacena todo en el arreglo la gestión de la
información para insertar y buscar se complica.
Descargar

Presentación de PowerPoint