GRUPO #4 - Método de Busqueda Secuencial y Binaria

DEFINE Y EXPLIQUE DE FORMA CLARA Y SENCILLA LOS MÉTODOS DE BÚSQUEDA SECUENCIAL Y BINARIA. DIFERENCIA FUNDAMÉNTALE, VENTAJAS Y DESVENTAJAS ENTRE AMBOS.

La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. A menudo 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.

Siendo el array de una dimensión o lista una estructura de acceso directo y a su vez de acceso secuencial, encontramos dos técnicas que utilizan estos dos métodos de acceso, para encontrar elementos dentro de un array: Búsqueda secuencial y búsqueda binaria.

Búsqueda secuencial.

La búsqueda secuencial, también se le conoce como búsqueda lineal.

Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la clave indicada (k) o hasta el final de la lista.

Este método consiste en recorrer el arreglo o vector elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del vector y se observa una casilla tras otra hasta que se encuentre 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 vector o arreglo no esta en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya se en el primer elemento, como en el ultimo. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del vector.

El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.

Ventaja:

Ø Es un método sumamente simple que resulta útil cuando se tiene un conjunto de datos pequeños (Hasta aproximadamente 500 elementos)

Ø Es fácil adaptar la búsqueda secuencial para que utilice una lista enlazada ordenada, lo que hace la búsqueda más eficaz.

Ø Si los datos buscados no están en orden es el único método que puede emplearse para hacer dichas búsquedas.

Desventaja:

Ø Este método tiende hacer muy lento.

Ø Si los valores de la clave no son únicos, para encontrar todos los elementos con una clave particular, se requiere buscar en todo el arreglo, lo que hace el proceso muy largo.

Búsqueda Binaria.

La búsqueda binaria es el método, donde si el arreglo o vector esta bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray 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.

Este método se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los pre – requisitos para la búsqueda binaria son:

Ø La lista debe estar ordenada, en un orden especifico de acuerdo al valor de la clave.

Ø Debe conocerse el número de elementos.

Si el conjunto de elementos es grande, el tiempo de búsqueda se puede reducir utilizando el siguiente algoritmo de tipo divide y vencerás:

Ø Se divide el elemento en dos partes.

Ø Se determina la parte que debe contener la clave buscada.

Ø Se repite el proceso en esa parte.

Una forma razonable de dividir el conjunto de elementos es mantener los elementos ordenados y después utilizar los índices del arreglo ordenado para determinar la parte del arreglo sobre la que se va a trabajar.

Ventajas:

Ø Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda.

Ø Es el método más eficiente para encontrar elementos en un arreglo ordenado.

Desventajas:

Este método funciona solamente con arreglos ordenados, por lo cual si nos encontramos con arreglos que no están en orden, este método, no nos ayudaría en nada.

Diferencias entre ambos métodos.

En el caso del método de búsqueda binaria, los arreglos deben estar únicamente ordenados, como se planteo anteriormente, por su parte el método de búsqueda secuencial o lineal, puede emplearse tanto en arreglos pequeños, como en aquellos que no están ordenados.

En segundo orden, podemos ver que el método de búsqueda binaria, es el método más eficiente para encontrar elementos en un arreglo ordenado, lo contrario sucede con el método de búsqueda secuencial ya que este es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas.