ASIGNATURA:
ESTRUCTURA Y ORGANIZACIÓN DE DATOS
CLAVE:
TIC-1002
PROFESORA:
ING. ROMÁN NÁJERA SUSANA MÓNICA
TEMA:
EJEMPLO UN PROGRAMA QUE EMPLEE UN MÉTODO DE BÚSQUEDA EN
JAVA
(BÚSQUEDA BINARIA)
NOMBRE:
MELÉNDEZ CLARA DANEL
SEMESTRE: 3er GRUPO:3E
SALINACRUZ,
OAXACA; DICIEMBRE DEL 2014.
METODOS DE BUSQUEDA
La
búsqueda es la operación más importante en el procesamiento de información, ya
que permite recuperar datos previamente almacenados. El resultado de una
búsqueda puede ser un éxito, si se encuentra la información o un fracaso, si no
la encuentra.
La
búsqueda se puede aplicar sobre elementos previamente ordenados o sobre
elementos desordenados, en el primer caso la búsqueda es más fácil, en cambio
en el segundo se dificulta un poco más el proceso, sobre todo cuando de se
trata de encontrar una cantidad de elementos similares.
Los
métodos de búsqueda se clasifican en:
- Búsqueda interna.
- Búsqueda externa.
Búsqueda
interna.
La
búsqueda interna es aquella en la que todos los elementos de la estructura
estática (arreglo) o dinámica (lista ligada o árbol) se encuentran almacenados
en la memoria principal de la computadora.
Los
métodos de búsqueda interna más importantes son:
- Secuencial o lineal.
- Binaria.
- Hash (transformación de claves)
Secuencial.
El
método de búsqueda secuencial consiste en revisar la estructura de datos
elemento por elemento hasta encontrar el dato que estamos buscando, o hasta
llegar al final de la estructura de datos.
Normalmente
cuando una función de búsqueda concluye con éxito, lo que interesa es conocer
en qué posición fue encontrado el elemento buscado.
La
búsqueda secuencial se puede aplicar a estructuras de datos ordenadas o
desordenadas.
Si
se aplica a una estructura desordenada y el elemento que se está buscando
existe más de una vez en la estructura, el proceso de búsqueda debe continuar hasta que se llegue al fin de la estructura.
El método de búsqueda binaria divide
el total de los elementos en dos, comparando el elemento buscado con el
central, en caso de no ser iguales, se determina si el elemento buscado es
menor o mayor al central, para determinar si la búsqueda continua del lado
izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de
división y comparación, hasta encontrar el elemento buscado o que la división
ya no sea posible.
Debemos destacar que este método de búsqueda
solo funciona con estructuras de datos previamente ordenadas, dividiendo cada
vez a la mitad el proceso de búsqueda, lo que hace que el método sea más
eficiente.
Ejemplo. Si tenemos una
estructura ordenada 0, 1, 2, 3, 5, 5, 5, 7, 8, 9 y estamos buscando el número
5, el resultado de la búsqueda nos mostraría la posicione 4 y el
proceso terminaría ya que el elemento buscado no es diferente al que esta en la
posición central.
|
Elementos
|
0
|
1
|
2
|
3
|
5
|
5
|
5
|
7
|
8
|
9
|
|
Posiciones
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
Posiciones donde
encontró el número 5
|
i
|
|
|
|
√
|
|
|
|
|
F
|
Este proceso debe sumar la posición inicial y la
final, dividiendo el resultado de la suma entre dos para obtener la posición central
generada por el cociente de la división, en este caso es (0+9)/2 = 4, esta
posición se compara con el elemento que estamos buscando y como son iguales la
búsqueda se detiene mostrando la posición donde lo encontró.
EJEMPLO
DE UN PROGRAMA EN JAVA (METODO BINARIO)
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
es el elemento que se busca, entonces la búsqueda finaliza, pero si no 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 y se comienza
comparando con el elemento central.
Implementación
del algoritmo de búsqueda binaria de manera no recursiva en Java. Se utiliza
una función estática de la clase BusquedaAlgoritmo. Recordar que para que
funcione correctamente los valores del arreglo deben estar ordenados.
public static int buscar( int
[] arreglo, int dato) {
int inicio = 0;
int fin = arreglo.length - 1;
int pos;
while (inicio <= fin) {
pos = (inicio+fin) / 2;
if ( arreglo[pos] == dato )
return pos;
else if ( arreglo[pos] < dato ) {
inicio = pos+1;
} else {
fin = pos-1;
}
}
return -1;
}
}
public static void main (String args[]) {
// Llenar arreglo
int [] edades = new int [35];
for (int i = 0; i < edades.length ;
i++)
edades[i] = i*i ;
// Mostrar arreglo.
for (int i = 0; i < edades.length ;
i++)
System.out.println ( "edades["+i+"]: "+
edades[i]);
int resultado =
BusquedaAlgoritmo.buscar(edades, 9);
if (resultado != -1) {
System.out.println ( "Encontrado en: "+
resultado);
} else {
System.out.println ( "El dato no se encuentra en el
arreglo, o el arreglo no está ordenado."
);
}
}
}
Para
poder ejecutar el Método de Búsqueda Binaria, se debe de contar con un Array
ordenado. El procedimiento que se realiza es el siguiente:
•EL
Programa internamente selecciona el elemento central del Array.
•Si
el elemento a buscar es el dato central el proceso termina. •Si el elemento a
buscar no coincide con el elemento central, continua la búsqueda:
•Se
subdivide en dos partes al Array.
•Si
el elemento a buscar es menor que el dato central, entonces selecciona la mitad
de la parte izquierda.
•La
parte seleccionada se subdivide nuevamente y se repite todo el proceso.
•El
proceso termina cuando el dato es encontrado; teniendo en cuenta que el dato a
buscar no puede encontrarse en el Array.
No hay comentarios:
Publicar un comentario