Estructura de datos

UNIDAD 8. MÉTODOS DE BUSQUEDA

La búsqueda se refiere a la operación de encontrar la posición de un elemento, entre un conjunto de ellos. Existen diferentes algoritmos para realizar una búsqueda.La operación de búsqueda de un elemento consisten en:

1. Determinar si el número pertenece al conjunto y en ese caso indicar su posición en el.

2. Determinar si el número no perteneceal conjunto

Los métodos de búsqueda más comunes son:

• Búsqueda Secuencial o Lineal
• Búsqueda Binaria
• Búsqueda por Transformación de claves (HASH)

Búsqueda Secuencial olineal

El método más sencillo de búsqueda en un conjunto de datos almacenados en secuencia, como un arreglo, es recorrer este arreglo posición por posición. Esta búsqueda compara cada elemento delvector con el valor deseado hasta que este se encuentra o hasta que se termine de recorrer el arreglo.

Búsqueda Binaria

En una búsqueda secuencial se comienza con el primer elemento del vector yse busca en el hasta que se encuentra el elemento deseado o bien hasta que se alcanza el final del vector. Este puede ser un método adecuado para pocos datos pero se requiere una técnica más eficazpara grandes conjuntos de datos.

La búsqueda binaria utiliza el método de “Divide y Vencerás”. 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 en la segunda mitad de la lista y a continuación se repite el proceso utilizando ahora elelemento central de esa sublista.

Debido a la naturaleza del proceso los elementos del arreglo deben estar previamente ordenados.

liz=0;
lde=nmax-1;
c=(liz+lde)/2;
while(liz!=lde &&A[c]!=bus)
{ if(bus>A[c])
liz=c+1;
else
lde=c-1;
c=(liz+lde)/2;
}
if (A[c]==bus)
System.out.println("Encontrado en pos: "+c);
else System.out.println("El numero no...