Algoritmos de Búsquedas“Búsqueda Lineal”

Concepción-TalcahuanoIngeniería en InformáticaAnálisis de Algoritmos

Nombre Alumno (s): Nelson Silva.

Paz

Morales.

Claudio

Marín.

Héctor Rifo.

INDICE

1. introducción.....................................................................................................3

2. Algoritmos de búsqueda.................................................................................4

2.1 Búsqueda lineal.........................................................................................4

2.1.1 Complejidad de la búsqueda lineal...................................................4

2.2 Búsqueda binaria......................................................................................7

2.3 Búsqueda mediante transformación de claves (Hashing)..................10

2.3.1 Truncamiento....................................................................................10

2.3.2 Plegamiento......................................................................................11

2.3.3 Aritmética modular...........................................................................12

2.3.4 Mitad cuadrado.................................................................................13

3. conclusión......................................................................................................14

1. INTRODUCCIÓN

En el siguiente informe se tomará el tema de la búsqueda de datos en Algoritmos, la cual tiene múltiples opciones del manejo de datos que presentan distintos casos de éxitos, el peor, el promedio y el mejor.

Además de tratar con estos casos se analizará su eficacia, eficiencia y calidad de búsqueda para cada tipo de opciones.

Página 3

2. ALGORITMOS DE BÚSQUEDA

2.1 Búsqueda lineal

La búsqueda lineal es sencilla de implementar e intuitiva. Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta llegar al último elemento del vector ó haber logrado encontrar dicho elemento antes de llegar al final. Si encuentra el elemento, entregara un mensaje positivo, como: "existe el elemento", además de poder entregar la posición de dicho elemento (índice). Y en caso contrario, entregara un mensaje negativo, como: "el elemento no existe". Esta búsqueda no requiere ningún requisito por parte del vector, por consiguiente no requiere que el vector este ordenado, tampoco qué sea par o impar.

2.1.1 Complejidad de la búsqueda lineal

Mejor Caso:

Es cuando la búsqueda termina tan pronto encuentra el elemento buscado en el array. Si tenemos suerte, puede ser que la primera posición examinada contenga el elemento que buscamos, en cuyo caso el algoritmo informará que tuvo éxito después de una sola comparación.

Ejemplo:

0 1 2 3 4 5 6 7 8 9

12 32 77 8 51 63 70 24 4 39

Buscar el elemento "12"

1.-12 = 12 Fin de la búsqueda2.-Mensaje"Elemento existe" posición 0

Página 4

Peor Caso:

Sucede cuando el elemento se encuentra en la última posición del array.

Ejemplo:

0 1 2 3 4 5 6 7 8 9

12 32 77 8 51 63 70 24 4 39

Buscar el elemento "39"

1.- 12 ≠ 39 2.- 32 ≠ 393.- 77 ≠ 394.- 8 ≠ 395.- 51 ≠ 396.- 63 ≠ 397.- 70 ≠ 398.- 24 ≠ 399.- 4 ≠ 3910.- 39 = 39 Fin de la búsqueda11.- Mensaje "Elemento existe" posición 9

Página 5

Promedio:

Ocurre cuando el elemento a buscar, se encuentra en la posición de en medio (n/2).

Ejemplo:

0 1 2 3 4 5 6 7 8 9

12 32 77 8 51 63 70 24 4 39

Buscar el elemento "51"

1.- 12 ≠ 39 2.- 32 ≠ 393.- 77 ≠ 394.- 8 ≠ 395.- 51 = 51 Fin de la búsqueda6.- Mensaje "Elemento existe" posición 4

Página 6

2.2 Búsqueda binaria

El algoritmo de búsqueda binaria es un excelente método para buscar datos dentro de una estructura (generalmente un arreglo unidimensional). Se le da el nombre de búsqueda binaria por que el algoritmo divide en dos el arreglo, aludiendo al concepto de bit, el cual puede tener dos estados.

Para este algoritmo se utiliza el concepto "Divide y vencerás".

Requisito:

Los datos del vector deben estar ordenados.

Procedimiento:

Primero se compara el elemento central del vector con el dato que se quiere buscar; si este es el elemento buscado, entonces la búsqueda se termina.

Si el elemento no es el que se busca, se comprueba si el elemento a buscar es mayor o menor al elemento central y si está en la primera o segunda mitad del vector.

Si el elemento es menor, se vuelve a tomar el elemento central de la primera mitad y la otra se elimina.

Si el elemento es mayor, se toma el elemento central de la segunda mitad y la otra se elimina.

Este proceso se repite hasta que se encuentre el elemento que se busca.

Página 7

Ejemplo:

Se puede aplicar en listas lineales como en arboles binarios de búsqueda. Se debe conocer el número de registros.

Mejor caso:

La búsqueda binaria requiere solo una comparación; esto significa que su tiempo de ejecución óptimo no depende de la cantidad de datos.

El esfuerzo mínimo es 1.

Caso promedio:

El promedio 1/2log2n.

Página 8

Peor caso:

El algoritmo de búsqueda binaria progresivamente va disminuyendo el número de elementos sobre el que se realiza la búsqueda a la mitad. Así, tras log2n divisiones se habrá localizado el elemento o se tendrá la seguridad de que no estaba.

El esfuerzo máximo para este algoritmo es log2n.

Página 9

2.3 Búsqueda mediante transformación de claves (Hashing)

Permite en aumentar la velocidad de búsqueda sin necesidad de tener lo elementos ordenados.

Consiste en transformar claves numéricas o alfanuméricas en direcciones o índices de un vector.

Existen 4 métodos de transformación de claves:

Truncamiento Plegamiento Aritmética modular Mitad del cuadrado

2.3.1 Truncamiento

Este método ignora parte de la clave y se deja la parte restante como índice. Para el caso de que la clave sea de 8 dígitos y tenga 1000 posiciones, entonces se toma el 1°,2° y 5° digito de izquierda a derecha.

Ejemplos:

Vector: 1000 posiciones Tamaño clave: 8Elementos: 1,2 y 5

N° Elementos

Clave

H(clave)= 481

Vector: 800 posiciones

0 1 2 3 4 5 6 7

7 4 8 7 2 1 9 5

Página 10

Tamaño clave: 8Elementos: 1,5 y 3

N° Elementos

Clave

Si H(clave)>vector

H(clave)=834 834 – 800 = 34

2.3.2 Plegamiento

Consiste en dividir la clave en diferentes partes y combinarlas para obtener el índice.

Todas las partes a excepción de la última debe obtener el mismo número de dígitos que el tamaño del vector.

Vector: 100 posicionesClave: 52136984

H(clave)= 521+369+84

H(clave)= 974 974 = 74

Se trunca

Se trunca

0 1 2 3 4 5 6 7

9 8 2 4 1 3 5 7

521 369 84

Página 11

2.3.3 Aritmética modular

Consiste en dividir la clave por el número de posiciones del vector donde el resultado es el resto de la división.

H(x)= x MOD m

x= clavem= tamaño del arreglo

Ejemplo:

Vector: 100 posiciones Clave: 43276581H(clave)=43276581 MOD 100H(clave)=81

Página 12

2.3.4 Mitad cuadrado

Consiste en calcular el cuadrado de la clave y tomar los dígitos centrales de este resultado.

H(x)=X^2

x= clave

Ejemplo:

Vector: 100 posiciones Clave: 5478

H(clave)=5478 * 5478

N° Elementos

Clave

Elementos centrales =3 y 4H(clave)= 08

0 1 2 3 4 5 6 7

3 0 0 0 8 4 8 4

Página 13

3. CONCLUSIÓN

Dada la investigación, se visualizan distintos datos, ordenados de tal manera que los algoritmos de búsqueda son ideales para distintos casos.

Los métodos aprendidos, son los siguientes:

Búsqueda lineal Búsqueda binaria Búsqueda mediante transformación de claves Truncamiento Plegamiento Aritmética modular Mitad cuadrado

Cada uno de ellos muestra desarrollos y son utilizados como métodos de orden y búsqueda de datos. Como mayor parte, se utiliza en 2 puntos.

1. Determinar si el elemento buscado se encuentra en el conjunto en el que se busca.

2. Si el elemento está en el conjunto, hallar la posición en la que se encuentra.

Página 14