Busqueda

Es el proceso de encontrar un elemento especifico de un array tecnincas de busqueda: secuencial y binaria

es necesario que los datos esten ordenados por algun algoritmo

BUSQUEDA SECUENCIAL

Está diseñada 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.

• Se utiliza cuando algún elemento 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 .

VENTAJAS Y DESVENTAJAS

• DESVENTAJA.- en un vector de N posiciones este algoritmo va a buscar posición a posición hasta dar con el dato solicitado y en el caso de que no exista pues también va a recorrer todo el arreglo.

• VENTAJA.- Lo bueno de este tipo de búsqueda es que es muy sencillo de implementar.

CODIGO


["aarona","aashta","abelarda","abelia","abigail","abril"] , todos de

tipo String y queremos saber si ya existe el nombre : "Abigail" en nuestro vector entonces tenemos que hacer lo siguiente:

public class BSecuencial {

public static void main(String[] args) throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ",
"Abril"};

System.out.print("Digite el nombre que desea buscar: ");
String nombre = entrada.readLine();
// entrada de dato a buscar


for (int i=0; i<VectorNombres.length;i++){

if(nombre.equalsIgnoreCase(VectorNombres[i])){

JOptionPane.showMessageDialog(null,"Elemento encontrado "+VectorNombres[i],"Encontrado",
JOptionPane.INFORMATION_MESSAGE);
encontrados++;
continue;
}
}

if(encontrados == 1 ){
System.out.println("Fin de busqueda, encontrado "+encontrados+" elemento igual");
}else{
System.out.println("Fin de búsqueda, encontrados "+encontrados+" elementos iguales");

BUSQUEDA BINARIA

Se situa la lectura en el centro de la lista y se comprueba se la clave coincide con el valor del elemento central.

si no se encuentra el valor de la clave se situa en la mitad inferior o superior del elemento central de la lista

Para utilizar este algoritmo, el array debe estar ordenado. La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina.

Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:

Se toma el elemento central y se divide el array en dos: {1,2,3,4}−5-{6,7,8,9} Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4} Se vuelve a dividir el array en dos: {1}−2-{3,4} Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4} Se vuelve a dividir en dos: {}−3-{4} Como el elemento buscado coincide con el central, lo hemos encontrado.

Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array.