martes, 17 de abril de 2012

PROGRAMACION: METODOS DE BUSQUEDA BY RODRIGO MORALES LARA



Algoritmo de búsqueda

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

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.

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 arreglo 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 arreglo.

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

Búsqueda dicotómica (binaria)

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado.

Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

Búsqueda burbuja

El método de intercambio directo, conocido coloquialmente con el nombre de la burbuja, es el mas utilizado entre los estudiantes principiantes de computación.

La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.

Se realizan (n-1) pasadas, transportando en cada de las mismas el menor o mayor elemento (según sea el caso) a su posicion ideal.


Búsqueda por interpolación


Este método se puede aplicar solamente a tablas o archivos ordenados. Como su nombre lo indica se trata de llegar al elemento buscado por medio de la interpolación lineal. El procedimiento es recursivo; como en el caso de la búsqueda binaria, en cada paso se van modificando los límites, disminuyendo el intervalo, hasta llegar al elemento buscado.

Si se determina que la clave buscada XX se encuentra dentro del intervalo INTABLA de la tabla, y que la variación en ese intervalo de la clave es INCLAVE, la siguiente posición a probar es:

PX = PI + ENTERO ((XX-XI) * (INTABLA / INCLAVE))

El algoritmo es similar al de búsqueda binaria, la diferencia está en que en vez de dividir el área en mitades, se delimita por medio de los valores resultantes de la interpolación.

En búsqueda binaria el espacio se corta siempre adentro a medias, las garantías de lo que desea el funcionamiento logarítmico. Sin embargo, durante la búsqueda encontramos un valor que esté muy cerca del número z de la búsqueda, parece más razonable continuar la búsqueda en esa area envez de ocultor e ir a la media punta siguiente.

En detalle, si z es muy pequeño, debemos comenzar la búsqueda en alguna parte en el principio de la secuencia en vez de la punta intermedia Considere la manera que abrimos un libro cuando estamos buscando para cierta página. Diga que la página es 200 y el libro parece de 800 paginas. La paginación 200 es así alrededor de la marca de un cuarto, y nosotros utilizamos este conocimiento como indicación de donde abrir el libro. No golpearemos probablemente la paginación 200 en el primer intento; suponga que conseguimos la paginación 250 en lugar de otro. Ahora cortamos la búsqueda a un rango de 250 paginas, y la paginación deseada está en alrededor la marca de 80 por ciento entre la paginación 1 y 250. Ahora intentamos ir detrás de un quinto de la manera corta. Podemos continuar este proceso hasta que conseguimos bastante cercanos a la paginación 200, de que que podemos mover de un tirón una pagina al mismo tiempo. Ésta es exactamente la idea detrás de la búsqueda de la interpolación. En vez de cortar el espacio de la búsqueda por una mitad fija, la cortamos por una cantidad que se parezca la más probable tener éxito.

El funcionamiento de la búsqueda de la interpolación depende no solamente de la talla de la secuencia, pero también de la entrada de información misma. Hay entradas de información para los chequeos de la búsqueda de interpolación del deseado en cada número en la secuencia. Sin embargo, la búsqueda de la interpolación es muy eficiente para las entradas de información que consisten en elementos relativamente uniformemente distribuidos (las paginaciones de un libro, por supuesto, se distribuyen uniformemente). Puede ser mostrado que el número medio de comparaciones se realizó por la búsqueda de interpolación, donde el promedio asume el control todas las secuencias posibles, es 0 (logn del registro). Aunque éste se parece ser un orden de la mejora magnitud concluída de el funcionamiento de la búsqueda binaria ( debido al logaritmo adicional).