DESARROLLO CONCEPTO MÉTODOS DE BÚSQUEDA

MÉTODOS DE BÚSQUEDA

DESARROLLO

CONCEPTO MÉTODOS DE BÚSQUEDA:

Los métodos de búsqueda permiten recuperar información de un vector o un archivo, que contenga una lista de datos. Por ejemplo se puede obtener el nombre y el número telefónico de nuestra agenda de contactos o la nota obtenida por un alumno en la lista de un curso.

Cuando se realizan búsquedas sobre vectores, se desea es encontrar la posición que ocupa el elemento buscado dentro de la lista de elementos que contiene el vector. Para la búsqueda de información en archivos es necesario realizar la búsqueda a partir de un campo clave dentro del archivo.

Existen diferentes métodos de búsqueda y se puede determinar con cual método trabajar dependiendo de la cantidad de elementos que existan en el vector o la organización de dichos elementos.

A continuación para determinar si un elemento pertenece a un conjunto de elementos e indicar su posición dentro de un vector, se utilizaran los métodos de búsqueda secuencial (lineal) y búsqueda binaria.

MÉTODOS DE BÚSQUEDA UTILIZADOS:

 Búsqueda Secuencial o Lineal:

En este método se recorre el vector desde el primer elemento hasta el último, comparando cada elemento del vector con el valor buscado, hasta que se encuentre el elemento o se llegue al final del vector. Este método es recomendado para realizar búsquedas con pocos datos.

Implementación del método que busca lineal o secuencial, y devuelve la posición del dato a buscar que se pasa como parámetro:

//Implementación del método que busca lineal o secuencialmente sobre los datos del vector. public int busquedaLineal(int dato){ int i; //Variable para controlar el ciclo while. int posicion; //Variable que devuelve la posición en la que se encuentra el elemento buscado. //Se Asigna el valor de -1 a la variable posición para devolver este valor en el supuesto caso de //que no se encuentre el valor buscado dentro del vector. posicion = -1; i = 0; //Mientras que no se llegue al final del vector y no se haya encontrado el dato buscado en el vector. while ((i <= getNumElementos()-1) && (posicion == -1)){ //Si el contenido del vector en la posición i-esima es igual al dato que se está buscando, entonces

//el dato si está en el vector y se devuelve la posición en donde se encuentra el dato dentro del //vector. Si no, es porque el dato no se encuentra en esa posición, y se incrementa la posición (i) //para una nueva comparación. if (getVectorDatos(i) == dato){ posicion=i; }else{ i=i+1; } } return posicion; }

 Búsqueda Binaria:

Este método es una técnica eficaz para realizar búsquedas en vectores o archivos que contengan un mayor número de datos. Este método divide el vector en mitades de manera sucesiva hasta que encuentra el dato buscado, es decir, el método divide el vector y se examina el elemento central del vector.

Si el elemento central es el dato que se busca, entonces la búsqueda finaliza, pero sino, se determina si el dato buscado está en la primera o la segunda mitad del vector y se repite el proceso en la nueva mitad, buscando su elemento central.

Para realizar la búsqueda binaria el vector debe estar ordenado, por esta razón hay que utilizar uno de los métodos ya estudiados; luego de tener el vector ordenado, se comienza comparando con el elemento central.

Implementación del método que busca de manera binaria, y devuelve la posición del dato a buscar que se pasa como parámetro:

public int bsuquedaBinaria(int dato){ int posicion, izq, der, centro; //Estas 4 variables almacenan posiciones del vector. ordenarIntercambio(); //Para realizar la búsqueda el vector debe estar ordenado. izq = 0; //Primera posición del vector. der = getNumElementos()-1; //Ultima posición del vector. //Se asigna el valor de -1 a la variable posición para devolver este valor en el supuesto caso de que //no se encuentre dato buscado dentro del vector. posicion = -1; //Mientras que no se llegue al final del vector y no se haya encontrado el dato buscado en el vector. while ((izq <= der) && (posicion == -1)){ //Se busca cual es la posición del dato que se encuentra en el centro del vector. centro = (izq + der) / 2; //Si el dato buscado es igual a lo que tiene el vector en la posición del centro entonces ya se encontró el //elemento buscado y se devuelve la posición en donde se encontró, pero sino, entonces //se determina si el elemento está a la izquierda o a la derecha del vector. Y se procede a buscar el //dato hacia el inicio del vector (izquierda) o hacia el final del vector (derecha), esto si el dato //buscado es mayor o menor al elemento que se encuentra en el centro del vector. if (dato == (getVectorDatos(centro)) ){ posicion = centro; }else{ if (dato < (getVectorDatos(centro))){

der = centro-1; }else{ izq = centro+1; } } } return posicion; }

IMPLEMENTACIÓN DE LOS MÉTODOS DE ORDENAMIENTO EN JAVA:

 Ejercicio propuesto implementado en Java

A continuación se implementa un ejercicio que permite almacenar una cantidad específica de códigos en un vector y posteriormente se implementan los métodos de búsqueda descritos anteriormente, para determinar si un código pasado como dato de búsqueda se encuentra almacenado dentro del vector.

 Diseño de clases UML de la solución

 Implementación de la clase MetodosBusqueda en el fichero MetodosBusqueda.java

En esta clase se implementan los métodos de búsqueda binaria y búsqueda secuencial. Igualmente se implementa un método de ordenamiento, necesario para ordenar el vector y realizar la búsqueda binaria.

public class MetodosBusqueda { //Se declaran los atributos de la clase, en este caso se declara el vector (vectorDatos). //y un atributo para asignar el número de elementos que tendrá el vector (numElementos). private int vectorDatos[]; private int numElementos; //posteriormente se implementa el método constructor de la clase para asignar los valores //iniciales de los atributos. public MetodosBusqueda(){ vectorDatos = null; numElementos = 0; } //El siguiente método crea el vector en tiempo de ejecución, posteriormente se asignara su tamaño. public void crearVector(){ vectorDatos = new int[numElementos]; } //Se

...