MÉTODOS DE BÚSQUEDA
INSTITUTO TECNOLÓGICO SUPERIOR DE HUETAMO .
INGENIERÍA EN SISTEMAS COMPUTACIONALES
Profesor: ing. José
Antonio Narciso Vera
Integrantes:
Eric Estrada Paredes
17070005
Ma. De los Angeles Medina Gómez 17070017
Rafael de Jesús Ruiz Castillo 17070025
INSTRUCTION
The result of a search can be a success, if the information
is found or a failure, if it is not found.
The search can be applied on previously ordered elements or
on disordered elements, in the first case the search is easier, on the other
hand, the process becomes more difficult in the second, especially when it
comes to finding a quantity of similar elements .
INTRODUCCIÓN
El resultado de una búsqueda puede ser un éxito, si se encuentra la información o un fracaso, si no la encuentra.
La búsqueda se puede aplicar sobre elementos previamente ordenados o sobre elementos desordenados, en el primer caso la búsqueda es más fácil, en cambio en el segundo se dificulta un poco más el proceso, sobre todo cuando de se trata de encontrar una cantidad de elementos similares.
Método de Búsqueda Secuencial
◦La búsqueda secuencial consiste en ir buscando en todos los
ítem de una lista ,trasladándonos de uno en uno siguiendo en orden secuencial
subyacente hasta que encontremos lo que buscamos o nos quedemos sin ítems,
hemos descubierto que el ítem que estábamos buscando no esta presente
VENTAJAS
◦Analiza todos los números de la lista
◦Una lista secuencial puede tener dos valores
◦No es necesario que la lista este ordenada
DESVENTAJAS
◦Es mas tardado ala hora de buscar ya que analiza todos los
elementos
Método de búsqueda binaria
◦Se le da el nombre de búsqueda binaria por que el algoritmo
divide en dos el arreglo, Está altamente recomendado para buscar en arreglos de
gran tamaño. La única condición para usar este algoritmo es que los datos
dentro del arreglo estén ordenados de menor a mayor.
Ventajas
◦Es un método eficiente si vector están ordenado.
◦Reduce el tiempo a la hora de buscar los ítem
◦Su ventaja es con los archivos extensos
◦El código de procedimiento es mas corto que los demás.
Desventajas
◦El archivo debe estar ordenado y el almacenamiento de un
archivo ordenado suele plantear problemas en las inserciones y eliminaciones de
elementos.
◦No revisa todos los elementos del archivo, requiere que
todos los elementos estén ordenados
Método de búsqueda por funciones de hash
Una tabla hash es una estructura de datos que permite pretender la inserción, búsqueda y borrado de elementos de tiempo constante para ello la función de dispersión debe calcularse en tiempo constante y distribución de forma uniforme los objetos a lo largo de la tabla.
La tabla hash debe tener un tamaño relativamente grande para reducir el numero de colisiones pero de igual manera no tan grande si no aumentaría el numero de dichas colisiones
Una colisión se produce cuando objetos diferentes dan lugar al mismo índice hash y es complicado evitar las colisiones
Formas de resolver las colisiones :
Resolución mediante exploración:
trata de buscar otra posición libre en la tabla para albergar la inserción del elemento.
Exploración lineal: visita la siguiente casilla. Si esta libre, realiza la inserción . Si no . Visita la siguiente casilla
Exploración cuadrática: visita la casilla ¡2 posiciones mas allá de la que causo la colisión si esta libre inserta. Si no repite el proceso hasta encontrar una libre
Resolución mediante encadenamiento enlazado:
En cada posición de la tabla se mantiene una lista enlazada en la que se van insertando los elementos cuyo valor hash les asigna la misma posición.
Hashing enlazado
El hashing en lazado usa un vector de listas enlazadas es decir son aquellos objetos que reciban un determinado valor de hash , se insertaran en la lista enlazada correspondiente
Ventajas
◦No es necesario tener los elementos ordenados
◦Almacenamiento asociativo
◦Recuperación eficiente de la información
Desventajas
◦Es difícil de implementar
◦No conviene implementarlo en arreglos pequeños por que
surgen muchas colisiones
CONCLUSIÓN
◦Todos los métodos de búsqueda interna tienen el propósito de encontrar un elemento, estos se buscan de manera ordenada como lo es el método secuencial o de forma binaria, es decir, a la mitad (dividiéndose en dos).
◦todos tienen un mismo fin su forma de desarrollar esa búsqueda es la que marca la diferencia de cada uno. Pueden llegar a ser tan fáciles o complejos como tu desees.
BIBLIOGRAFÍA
◦L. Joyanes Aguilar e I. Zahonero Martínez, Algoritmos y
estructuras de datos: una perspectiva en C (Primera edición). Editorial
McGraw-Hill, 2004.
◦
◦L. Joyanes Aguilar e I. Zahonero Martínez, Programación en
C: metodología, algoritmos y estructuras de datos (Segunda edición). Editorial
McGraw-Hill, 2005.
◦Introducción a la programación estructurada en C (Primera
edición). F. A. Martínez Gil y G. Martín Quetglás. Servicio de Publicaciones,
Universidad de Valencia. Junio, 2003
