Metodos de búsqueda

UAEM
FCAeI
ESTRUCTURA DE DATOS II

TRABAJO DE INVESTIGACION DE LA UNIDAD 3
“MÉTODOS DE BÚSQUEDA”

*BÚSQUEDA SECUENCIAL
*BÚSQUEDA BINARIA
*BÚSQUEDA DIRECTA
Alumno: Omar Pérez Pacheco
Licenciado en informática
4ºU L.I.

METODOS DE BUSQUEDA

Los métodos de búsqueda realizan una operación que tiene como finalidad la ubicación de un elemento dentro de la estructura de datos. Por logeneral un programador estará trabajando con grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si un arreglo contiene un valor que coincide con algún valor clave o buscado.
El resultado de la operación es el éxito en el caso de encontrar el elemento buscado y de fracaso en caso contrario. Ejemplos: Directorios de archivos ordenados. Ofertas laboralesordenados por tipo de trabajo. Libros de la biblioteca ordenados por autor y tema. Se puede realizar sobre elementos ordenados ó sobre elementos desordenados, entre estos métodos conseguimos tres tipos tales como:

BUSQUEDA SECUENCIAL
La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valorbuscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en elprimer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.
El método de búsqueda secuencial funciona bien con arreglos pequeños o para arreglos no ordenados.
* Ventajas.
1. Es eficiente cuando un arreglo no está ordenado es la única manera en la que se puede emplear.
* Desventajas.2. Es muy lento.
3. Requiere mucho tiempo, debido a que se comparan uno a uno.

Planteamos el problema de buscar un elemento dentro de un conjunto de ellos que pueden ser todos distintos. Para concretar más, supongamos que el problema es encontrar un número dentro de una lista.
Si la lista de números no tiene ningún tipo de orden poco más podemos hacer que recorrerla toda hasta queencontramos el buscado. El algoritmo de la búsqueda secuencial seguiría el siguiente pseudocódigo:

indice BLineal (Tabla T, clave K, dim N)
i = 0
mientras i < N && T[i] != k :
i++;
Si i == N :
devolver error
else
devolver i;
ALGORITMO:
Comenzar por el primer elemento de la lista mientras mas elementos en la lista yvalor clave no encontrado. Obtener siguiente elemento de la lista:
Si valor clave = encontrado
Entonces devolver registro encontrado
Si no devolver registro no encontrado

MÉTODO BINARIO
La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coincidenfinaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en la parte superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
VENTAJAS
*Este método es muy eficiente siempre que el vector esté ordenado. En la práctica, esto suele suceder, pero no siempre. Por esta razón la búsqueda binaria iterativa exige una ordenación previa del archivo.
* La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista.
* Es mas rápido, su mayor ventaja es con los archivos extensos.
* El código del...