La búsqueda binaria es un algoritmo ampliamente utilizado que opera en una lista o arreglo ordenado. Es eficiente y reduce el espacio de búsqueda a la mitad con cada comparación, lo que lo hace mucho más rápido que la búsqueda lineal para conjuntos de datos grandes. La búsqueda binaria se basa en el principio de dividir y conquistar. Comienza comparando el elemento del medio del arreglo ordenado con el elemento objetivo. Si coinciden, la búsqueda es exitosa. Si el elemento medio es mayor que el objetivo, la búsqueda continúa en la mitad izquierda del arreglo; si es menor, la búsqueda continúa en la mitad derecha. Este proceso se repite hasta que se encuentre el elemento objetivo o se agote el espacio de búsqueda.
El algoritmo Paso por Paso
- Calcula el índice medio del espacio de búsqueda (bajo + alto) / 2 .
- Compara el elemento medio con el elemento objetivo.
- Si coinciden, la búsqueda es exitosa.
- Si el elemento medio es mayor que el objetivo, reduce la búsqueda a la mitad izquierda (establece alto = medio – 1).
- Si el elemento medio es menor que el objetivo, reduce la búsqueda a la mitad derecha (establece bajo = medio + 1).
- Repite los pasos 1-5 hasta que se encuentre el objetivo o bajo sea mayor que alto.
Ejemplo de Programacion
A continuación, presentamos un ejemplo de implementación del algoritmo de la busqueda binaria en Java, junto con comentarios:
public class BusquedaBinaria {
public static int busquedaBinaria(int[] arr, int objetivo) {
int bajo = 0;
int alto = arr.length - 1;
while (bajo <= alto) {
int medio = bajo + (alto - bajo) / 2;
if (arr[medio] == objetivo) {
return medio; // Objetivo encontrado en el índice 'medio'
} else if (arr[medio] < objetivo) {
bajo = medio + 1; // Buscar en la mitad derecha
} else {
alto = medio - 1; // Buscar en la mitad izquierda
}
}
return -1; // Objetivo no encontrado
}
public static void main(String[] args) {
int[] arregloOrdenado = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
int objetivo = 23;
int resultado = busquedaBinaria(arregloOrdenado, objetivo);
if (resultado != -1) {
System.out.println("Objetivo encontrado en el índice " + resultado);
} else {
System.out.println("Objetivo no encontrado");
}
}
}
Complejidad Temporal
La búsqueda binaria tiene una complejidad temporal de O(log n), donde n es el número de elementos en el arreglo. Esto se debe a que el espacio de búsqueda se reduce a la mitad con cada comparación. El algoritmo es altamente eficiente para conjuntos de datos grandes en comparación con la búsqueda lineal, que tiene una complejidad temporal de O(n).
Conclución
La búsqueda binaria es un algoritmo poderoso para encontrar elementos en un arreglo ordenado de manera eficiente. Siguiendo los pasos descritos en este tutorial, puedes implementar la búsqueda binaria en Java y aprovechar su complejidad temporal logarítmica. Recuerda que la búsqueda binaria requiere un arreglo ordenado, así que asegúrate de que los datos de entrada estén ordenados antes de utilizar este algoritmo.
