estructuradedatosfimeuanl

Búsqueda

La recuperación de información es una de las aplicaciones más importantes de las computadoras. La búsqueda de información está relacionada con las tablas para consultas. Estas tablas contienen una cantidad de información que se almacenan en forma de listas de parejas de datos. Por ejemplo un catálogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos en una lista. Existen diferentes tipos de búsqueda, pero en este informe describiremos sólo la de tipo Secuencial y Binaria.

Características:

· Puede ser binaria o secuencial

· Busca los datos de manera objetiva

· Es muy rápida la búsqueda siempre y cuando sepas que es lo que estás buscando

Aplicaciones:

Entre sus aplicaciones seria en las listas, tablas de consultas, etc., (todo lo relacionado a la computación)

METODOS DE BUSQUEDA
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
• Métodos de Búsqueda Interna
• Métodos de Búsqueda Externa.

METODOS DE BUSQUEDA INTERNA
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda más importantes son:
• Secuencial o lineal
• Binaria
• Por transformación de claves
• Arboles de búsqueda

METODOS DE BUSQUEDA EXTERNA
• Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).

Ventajas y desventajas:

Entre sus ventajas esta que te facilita el trabajo al momento de buscar una información en específico y ahorras tiempo y es muy rápida

Y sus desventajas es que debes saber que estás buscando, ya que si no podrás realizar una búsqueda eficiente.

Búsqueda Secuencial

Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del vector hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del vector. A continuación se muestra el pseudocódigo del algoritmo:

int busquedaSimple(int vector[n], int n, int dato) {

int i;

for(i=0; i<n; i++) {

if(dato==vector[i]) {

return i;

break;

}

return -1;

}

Funcionamiento

Consiste en ir comparando el elemento que se busca con cada elemento del arreglo hasta cuándo se encuentra. Busquemos el elementos “u”.

Características

Ø Intuitiva.

Ø Explora secuencialmente el vector.

Ø No requiere ningún requisito para el arreglo.

Ø Cuando el elemento no se encuentra tiene que realizar n comparaciones.

Ø El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero.

Ø Es directa y se basa en el uso de “fuerza bruta”.

Ventajas

ü Si la información se encuentra completamente desordenada es el único que nos podrá ayudar a encontrar el dato que buscamos.

ü Sencilla de implementar.

ü Funciona bien con arreglos pequeños y no ordenados.

Desventajas

û Su eficiencia es pobre, tiene complejidad lineal, O(n).

û Método de búsqueda más lento.

Eficiencia y Complejidad

Considerando la Cantidad de Comparaciones

Ø Mejor Caso

El elemento buscado está en la primera posición. Es decir, se hace una sola comparación.

Ø Peor Caso

El elemento buscado está en la última posición. Necesitando igual cantidad de comparaciones que de elementos el arreglo.

Ø En Promedio

El elemento buscado estará cerca de la mitad. Necesitando en promedio, la mitad de comparaciones que de elementos

Por lo tanto, la velocidad de ejecución depende linealmente del tamaño del arreglo.

Aplicaciones

Los archivos secuenciales son típicamente utilizados en aplicaciones de proceso de lotes Y son óptimos para dichas aplicaciones si se procesan todos los registros. La organización secuencias de archivos es la única que es fácil de usar tanto en disco como en cinta.

Un ejemplo claro para utilizar esta técnica de búsqueda es cuando se tiene una base de datos no muy grande en un negocio pequeño donde los registros más usados son llamados con frecuencia, es aquí donde esta técnica es fuerte, ya que se aplica a un patrón de búsqueda pequeño, sencillo y manejable; es decir como si fuera una descripción, es uno tras otro.

Una aplicación de la búsqueda puede ser en:

v Vector

Se recorre el vector de izquierda a derecha hasta encontrar una componente cuyo valor coincida con el buscado ó hasta que se acabe el vector. En este último caso el algoritmo debe indicar la no existencia de dicho valor. Este método es válido para vectores ordenados o no, aunque para los vectores ordenados veremos otros métodos más eficientes.

v Vector Ordenado

Cuando el vector de búsqueda esta ordenado se consigue un algoritmo más eficiente, sin más que modificar la condición de fin del caso anterior. La ventaja que se obtiene es que una vez sobrepasado el valor buscado, no es necesario recorrer el resto del vector para saber que el valor no existe.

v Matriz

Se realiza mediante el anidamiento de dos bucles de búsqueda HASTA cuya finalización vendrá dada por la aparición del valor buscado o la terminación de la matriz. El recorrido se podrá hacer indistintamente por fila o por columna.

v Búsqueda de personas.

Se envía como parámetro las primeras letras del apellido, y nos devolverá una lista de las coincidentes y su índice.

v Se utiliza para casos de búsquedas al igual que de personas, pero puede ser en otros casos de números u otros elementos. Como las listas de datos.

¿Cuándo es conveniente usarlo?

Como se mencionó en las características, se puede usar en arreglos que no estén ordenados, o en términos más comunes en archivos que no se encuentran ordenados en un programa, ya que este método de búsqueda es el único que nos ayudara a realizar este proceso, ya que la binaria no puede realizar búsqueda en arreglos desordenados.

Búsqueda Binaria

La búsqueda binaria proporciona una técnica de búsqueda mejorada. Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. Dada la palabra, se abre el libro cerca del principio, dentro o del final de pendiendo de la primer letra del primer apellido o de la palabra que busca. Se puede tener suerte y acertar con la página correcta; pero, normalmente, no será así y se mueve el lector a la página anterior o posterior del libro. Por ejemplo, si la palabra comienza con “J” y se está en la “L” se mueve uno hacia atrás. El proceso continúa hasta que se encuentra la página busca o hasta que se descubre que la palabra no está en la lista.

Se selecciona el elemento del centro o aproximadamente del centro del array. Si el valor a buscar no coincide con el elemento seleccionado es mayor que él, se continúa la búsqueda en la segunda mitad del array. Si por el contrario, el valor a buscar es menor que el valor del elemento seleccionado, la búsqueda continúa en la primera parte del array. En ambos casos, se halla de nuevo el elemento central, correspondiente al nuevo intervalo de búsqueda, repitiéndose el ciclo. El proceso se repita hasta que se encuentra el valor a buscar, o bien hasta que el intervalo de búsqueda sea nulo, lo que querrá decir que el elemento buscado no figura en el array.

La búsqueda binaria al igual que otros algoritmos como el quicksort utiliza la técnica divide y vencerás. Uno de los requisitos antes de ejecutar la búsqueda binaria, es que el conjunto de elementos debe de estar ordenado.

Funcionamiento

¿Cómo funciona la búsqueda binaria?

Necesitamos una serie de datos para realizar la búsqueda: El elemento en la posición inicio, fin, medio. Y por supuesto el tamaño del vector y elemento que queremos buscar.

int bajo = 0;

int medio = 0;

int alto = arraySize - 1;

medio = (bajo + alto) / 2;

Preguntamos si el elemento buscado es igual al elemento que se encuentra en la posición medio del array, si es afirmativo ya encontramos el elemento y no hay nada más que hacer.

if (searched == array[medio]) {

cout << "Se encuentra en la posición " << medio + 1 << endl;

return array[medio];

}

Si no es así. Preguntamos si el elemento que se encuentra en la posición medio es mayor al elemento buscado, si es afirmativo y como el arreglo está ordenado, quiere decir que elemento buscado es menor al del medio. Entonces ahora solo buscaríamos en esa división del arreglo, por lo tanto, el fin ahora sería el elemento anterior al medio.

if (array[medio] > searched) {

alto = medio - 1;

}

De lo contrario quiere decir que elemento buscado es mayor al del medio, entonces debemos buscar en la otra división del arreglo, por lo tanto el inicio sería el elemento posterior al medio.

else {

bajo = medio + 1;

}

Con cualquiera de estas 2 operaciones descartamos la otra mitad del arreglo y por lo tanto reducimos notablemente el número de iteraciones.

Por lo tanto, en cada iteración, la búsqueda se reduce a la mitad del array. Realizamos esto en un bucle mientras el inicio sea menor o igual al fin.

Características

Ø Sirve únicamente para arreglos ordenados.

Ø Es más eficiente que el método de búsqueda secuencial, debido a que el número de comparaciones se reduce a la mitad por cada iteración del método.

Ø Cantidad mínima de comparaciones con la que cuenta está búsqueda binaria es 1.

Ø Esta búsqueda termina cuando el elemento es encontrado o cuando el intervalo se anula, está vacío.

Ventajas

ü Es el método de búsqueda más eficiente.

ü Reduce al máximo el tiempo necesario para buscar un elemento dentro de una lista.

ü En un arreglo con gran cantidad de elementos, esta búsqueda desecha de una pasada la mitad de elementos para iniciar la operación.

ü El código del procedimiento de esta búsqueda es corto en comparación con las demás técnicas de búsqueda.

Desventajas

ü Funciona exclusivamente con arreglos ordenados.

ü No se pueden utilizar con listas simplemente ligadas porque no podríamos retroceder para establecer intervalos de búsqueda.

Aplicaciones

Ejemplo: Árbol Binario de Búsqueda:

Se distinguen 2 casos triviales con solución directa: árbol vacío (elemento no encontrado) o raíz del árbol.

Solución: Cuando el elemento no se encuentra en la raíz, dividimos el árbol en 2 subarboles (izquierda y derecha) y aplicamos ABB, sobre aquel que nos interese (al estar ordenado solo debemos ir por una de las ramas).

La combinación de resultados es trivial: la solución del subproblema es también la del problema global.

Supongamos la lista:

1231

1473

1545

1834

1892

1898 elemento central

1983

2005

2446

2685

3200

Si está buscando el elemento 1983, se examina el número central 1898 en la sexta posición. Ya que 1983 es mayor que 1898, se desprecia la primera sublista y nos centramos en la segunda:

1983

2005

2446 elemento central

2685

3200

El número central de esta sublista es 2446 y el elemento buscado es 1983 menos que 2446; eliminamos la segunda sublista y nos queda:

1983

2005

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.

CONCLUSION

Es indispensable tener en mente que el ordenamiento de datos va de la mano con la búsqueda ya qu epara uno de los metodos de esta función se requiere ordenar el arreglo donde se buscarán elementos. En esta investigación nos podemos dar cuenta cual método es más viable utilizar en dado caso del tamaño del arreglo o complejidad del programa.

IMPLEMENTACION

BusquedaBinaria.c

Busqueda Secuencial.c

DESCARGAR LA PRESENTACION EN POWER POINT