UNIDAD III
Métodos de Búsqueda
Introducción
Consiste en buscar un determinado elemento dentro de un vector dado. Si dicho elemento existe, se debe indicar la posición que ocupa dentro del vector, es decir, el índice.
- si el vector está desordenado:
Búsqueda secuencial, se trata de recorrer el vector uno a uno hasta encontrar el elemento a buscar.
- si el vector está ordenado:
Búsqueda binaria, se trata de ir acotando el intervalo de búsqueda en función del valor a buscar.
3.1 Búsqueda secuencial
El método más sencillo de buscar un elemento en un vector es explorar secuencialmente el. vector o, dicho en otras palabras, recorrer el vector desde el primer elemento al último. Si se encuentra el elemento buscado, visualizar un mensaje similar ‘Fin de búsqueda’; en caso contrario, visualizar un mensaje similar ‘Elemento no existe en la lista’.
En otras palabras, la búsqueda secuencial compara cada elemento del vector y, por consiguiente, no necesita estar ordenado. El recorrido del vector se realizará normalmente con estructuras repetitivas.
Si existe n elementos, se requerirán como media n/2 comparaciones para encontrar un determinado elemento. En el caso más desfavorable se necesitarán n comparaciones.
Este método no es completamente satisfactorio, ya que si t no está en el vector A, i toma el valor n+1 y la comparación
A[i] < > t
Producirá una referencia al elemento A[n+1], que presumiblemente no existe. Este problema se resuelve sustituyendo i<= n por i < n en la instrucción mientras, es decir, modificando la instrucción anterior mientras por
Mientras (A[i] < > t) y (i < n) hacer
Búsqueda secuencial con centinela
Una manera eficaz de realizar una búsqueda secuencial consiste en modificar los algoritmos anteriores utilizando un elemento centinela. Este elemento se agrega al vector al final del mismo. El valor del elemento centinela es el del argumento. El propósito de este elemento centinela, A[n+1], es significar que la búsqueda siempre tendrá éxito. El elemento A[n+1] sirve como centinela y se le asigna el valor de t antes de iniciar la búsqueda. En cada paso se evita la comparación de i con N y, por consiguiente, este algoritmo será preferible a los métodos anteriores, concretamente el método 4. Si el índice alcanzase el valor n+1, supondría que el argumento no pertenece al vector original y en consecuencia la búsqueda no tiene éxito.
Una variante del método 5 es utilizar una variable lógica (interruptor o switch), que represente la existencia o no del elemento buscado.
Localizar si el elemento t existe en una lista A[i], donde i varía desde 1 a n.
En este ejemplo se trata de utilizar una variable lógico ENCONTRADO para indicar si existe o no el elemento de la lista.
De todas las versiones anteriores, tal vez la mas adecuada sea la incluida en el método 6. Entre otras razones, debido a que el bucle mientras engloba las acciones que permiten explorar el vector bien hasta que t se encuentre o bien cuando se alcance el final del vector.
 |
El método de búsqueda lineal tiene el inconveniente del consumo excesivo de tiempo en la localización del elemento buscado. Cuando el elemento buscado no se encuentra en el vector, se verifican o comprueban sus n elementos. En los casos en que el elemento se encuentra en la lista, el número podrá ser el primero, el último o alguno comprendido entre ambos. Se puede suponer que el número medio de comprobaciones o comparaciones a realizar es de (n+1)/2 (aproximadamente igual a la mitad de los elementos del vector).
La búsqueda secuencial o lineal no es el método más eficiente para vectores con un gran número de elementos. En estos casos, el método más idóneo es el de búsqueda binaria, que presupone una ordenación previa en los elementos del vector. Este caso suele ser muy utilizado en numerosas facetas de la vida diaria. Un ejemplo de ello es la búsqueda del número de un abonado en una guía telefónica; normalmente no se busca el nombre en orden secuencial, sino que se busca en la primera o segunda mitad de la guía; una vez en esa mitad, se vuelve a buscar en una de sus dos submitades, y así sucesivamente se repite el proceso hasta que se localiza la página correcta.
3.2 Búsqueda binaria
En una búsqueda secuencial se comienza con el primer elemento del vector y se busca en él hasta que se encuentra el elemento deseado o se alcanza el final del vector. Aunque este puede ser un método adecuado para pocos datos, e necesita una técnica más eficaz para conjuntos grandes de datos.
La búsqueda binaria utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado, entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o la segunda mitad de la lista y, a continuación, se repite este proceso, utilizando el elemento central de esa sublista.
Ejemplo:
Si está buscando el elemento 1983, se examina el número central, 1898, en la sexta posición. Ya que 1983 es mayor que el elemento 1898, se desprecia la primera sublista y nos centramos en la segunda. El número central de esta sublista es 2446 y el elemento buscado es 1983, menor que 2446; eliminamos la segunda sublista y nos queda la 3ª sublista. Como no hay término central, elegimos el término inmediatamente anterior al término central 1983, que es el buscado. Se han necesitado tres comparaciones, mientras que la búsqueda secuencial hubiese necesitado siete.
La búsqueda binaria se utiliza en vectores ordenados y se basa en la constante del espacio de búsqueda (recorrido del vector). Se comienza comparando el elemento que se busca, no con el primer elemento, sino con el elemento central. Si el elemento buscado – t – es menor que el elemento central, entonces t deberá estar en la mitad izquierda o inferior del vector; si es mayor que el valor central, deberá estar en la mitad derecha o superior, y si es igual al valor central, se habrá encontrado el elemento buscado.
3.3 Búsqueda Hash
La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista. Sin embargo este método exige que los datos estén ordenados. Otro método que puede aumentar la velocidad de búsqueda en el que los datos no necesitan estar ordenados, se conoce como transformación de claves (clave dirección) o hashing. Nos permite encontrar directamente el registro buscado.
Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1) = R(k2).
Pero: K1 diferente de K2, decimos que hay colisión.
Ventajas:
- Se pueden usar los valores naturales de la llave.
- Se logra independencia lógica y física, ya que el valor de las llaves son independientes del espacio de direcciones.
- No requiere almacenamiento adicional.
Desventajas:
- No pueden usarse registros de longitud variable.
- No permite llaves repetidas.
- Solo permite acceso por una sola llave.
Costos:
- Tiempo de procesamiento requerido para la aplicación de la función Hash.
- Tiempo de procesamiento para solucionar colisiones.
Definición:
Consiste en convertir la clave dada (numérica o alfanumérica) en una dirección (índice) dentro del array. La correspondencia entre las claves y la dirección en el medio de almacenamiento o en el array se establece por una función de conversión (función o hash)
Función de conversión
1º Toma como entrada una clave (código del artículo)
2º y la convierte en el índice la tabla de conversión
Esta tabla puede ser representada como un array de tamaño n (índices de 0 a n-1), siendo n el número de registros del array.
Si H es la función de conversión y K es una de las claves (números de código), entonces el índice calculado se llama la conversión de la clave K.
División entera Módulo
1. H (k) = k div M 2. H (k) = k mod M
Donde: k es la clave, y M el tamaño de la tabla.
Hashing por residuo de división
Si se desea que las direcciones vayan de 0 hasta m-1. La función de conversión debe ser:
H(k) = k mod (M+1)
Ejemplo:
Un vector tiene 0..100 posiciones. Supongamos que las claves de búsqueda de los elementos de la tabla son enteros positivos.
H(k) = k mod 101
123445678 mod 101 = 44
123445880 mod 101 = 44
Se observa que con este método, dos claves diferentes producen el mismo índice (44). Este fenómeno se conoce como colisiones.
Solución a colisiones
Dada la clave k y el array de registros A.
- Calcular el índice H(k)= i.
- Si el índice o posición está ocupado (contiene un registro) por la clave buscada, entonces “Clave encontrada” en la posición A[H(k)]= A[i] y se termina el algoritmo.
- Si A[i] ya está ocupada (contiene un registro) y no se encuentra la clave buscada, se comprueba A[i+1], A[i+2], etc., hasta encontrarla; si se llega a la posición final, sin encontrar la clave3 buscada; se salta ala primera posición(1) y se sigue la comprobación.
EJERCICIO # 4: Programar búsquedas en arreglos
HERRAMIENTAS, MATERIALES Y EQUIPOS:
- Hojas blancas, lápiz
- Lenguaje C#
- Pc
PROCEDIMIENTO:
- Resuelva cada uno de los ejercicios de acuerdo al procedimiento que se indica.
- Elabore el algoritmo de cada uno de los problemas planteados.
- Codifique los algoritmos en Lenguaje C#.
- Compruebe que la ejecución y sus resultados sean correctos.
EVIDENCIAS
Documentos:
- Hoja de presentación
- Algoritmos de cada uno de los ejercicios.
- Diagramas de Flujo de cada método.
- Impresión del Código en el lenguaje C#.
- Impresión de la ejecución. (Pantalla con resultados)
- Conclusión.
Programas:
- Toda la carpeta
- Todos los ejercicios serán entregados en un solo disco. (El disco debe traer su etiqueta correspondiente).
PLANTEAMIENTO DE PROBLEMAS
Aplique el método de búsqueda secuencial, al ejercicio 2.1 (fechas de nacimiento) resuelto en la unidad 1.
- Aplique el método de búsqueda binaria, al ejercicio 2.2 (Agenda Telefónica) resuelto en la unidad 1.
- Aplique el método de búsqueda hash, al ejercicio 2.3 (Calificaciones) resuelto en la unidad 1. Recodifique de tal manera que permita la inserción con el método hash, considere que cada alumno tiene un número de matricula para identificarlo.
Conclusión
El método de búsqueda lineal de un determinado valor clave en un array, que compara cada elemento con la clave buscada, puede ser útil en arrays pequeños o no ordenados. Y el método de búsqueda binaria es mucho más eficiente pero requiere arrays ordenados.
Existe otro método de acceso directo a un determinado elemento o posición, aquí la información del array no tiene porqué ser colocada en forma secuencial. Es, por tanto, posible usar una función hash que transforme el valor clave en un número válido para ser utilizado como subíndice en el array y almacenar la información en la posición especificada por dicho subíndice. Aunque esta función no siempre proporciona valores distintos, y puede suceder que para dos claves diferentes devuelva la misma dirección. Esta situación se denomina colisión y se deben encontrar métodos para su correcta resolución.
|
