Búsqueda binaria en arrays ordenados en Java

Regresar al índice

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,15,17,20,45,51,60,68,74,75};
int mitad;
int limiteInferior = 0;
int limiteSuperior = numeros.length - 1;
int numeroBusqueda = 68;
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");
}
}

Espero haber ayudado en algo. Hasta la próxima oportunidad!

DESCARGAR PUBLICACIÓN

Regresar al índice

Twittear