Secuencial Binaria y Hash

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