Primero
que nada hay que saber que es un array:
Un array es
una estructura de datos que nos permite almacenar una gran cantidad de datos de
un mismo tipo. El tamaño de los arrays se declara en un primer
momento y no puede cambiar en tiempo de ejecución como puede producirse en
otros lenguajes.
Búsqueda
binaria en arrays ordenados
Para
buscar un elemento en un array ordenado se puede aplicar la técnica de la
búsqueda binaria.
El conjunto de búsqueda se delimita por dos posiciones: el
límite inferior y el límite superior.
El algoritmo empieza la búsqueda por el
elemento que está almacenado en la mitad del conjunto de búsqueda. Si el
elemento almacenado en la mitad del conjunto es mayor que el valor que se
busca, entonces continúa la búsqueda en la primera mitad. Si el elemento
almacenado en la mitad del conjunto es menor que el valor que se busca,
entonces continúa la búsqueda en la segunda mitad. Si el elemento almacenado en
la mitad del conjunto es igual que el valor que se busca, finaliza el proceso.
En cada comparación, el algoritmo reduce el conjunto de búsqueda a la mitad. Si
durante las sucesivas reducciones del conjunto de búsqueda el límite inferior es
mayor que el límite superior, entonces el valor que se busca no está en el
array y finaliza el proceso.
En
este ejemplo el conjunto de búsqueda tiene 10 elementos, el límite inferior
coincide con el primer elemento del array y el límite superior con el último
elemento del array.
Si
se aplica la búsqueda binaria para buscar el número 18, el algoritmo realiza
las siguientes reducciones del conjunto de búsqueda.
Cuando
se busca el número 18 en el array, en la primera iteración se compara el valor
almacenado en la mitad con el 18. La mitad es la posición 4
y almacena un 10. Como 18 es mayor que 10, se descarta la primera mitad del
conjunto de búsqueda y el límite inferior se hace igual a la mitad +
1. Ahora, el límite inferior es 5 y la nueva mitad es 7. Los valores del array
que se han descartado en esta iteración se han tachado.
Una
vez más, se compara el 18 con el valor almacenado en la mitad, que es 16.
Como 18 es mayor que 16, se descarta la primera mitad del conjunto de búsqueda
y el límite inferior se hace igual a la mitad + 1. Ahora, el límite inferior es
8 y la nueva mitad es 8. En la siguiente iteración se compara el valor
almacenado en la posición central con el 18 y finaliza el algoritmo.
En
este ejemplo, el algoritmo de búsqueda binaria ha realizado tres comparaciones
para encontrar el número 18 en el array.
Durante
el proceso de división del conjunto de búsqueda se modifica el valor del límite
inferior o del límite superior, dependiendo de si el número que se busca está
en la primera mitad o en la segunda mitad. Si durante este proceso el límite
inferior es mayor que el límite superior, entonces el algoritmo finaliza porque
el número que se busca no está en el array.
El
siguiente programa utiliza el algoritmo de búsqueda binaria para buscar un
número entre cero y 100 en un array de números ordenados.
public class
BusquedaBinaria {
public
static void main(String[] args) {
int[]
numeros = {1,2,3,4,6,7,8,9,10,16,17,19,45,59,60,68,74,85};
int mitad;
int
limiteInferior = 0;
int
limiteSuperior = numeros.length - 1;
int
numeroBusqueda = 45;
boolean
encontrado = false;
while
((limiteInferior <= limiteSuperior) && (!encontrado)) {
mitad =
(limiteInferior + limiteSuperior) / 2;
if
(numeros[mitad] == numeroBusqueda) {
encontrado =
true; // ¡encontrado!
}
else if
(numeros[mitad] > numeroBusqueda) {
limiteSuperior
= mitad - 1; // buscar en la primera mitad
} else {
limiteInferior
= mitad + 1; // buscar en la segunda mitad
}
}
if
(encontrado)
System.out.println("He
encontrado el número");
else
System.out.println("No
he encontrado el número");
}
}