En la búsqueda binaria, dado un array (también llamado arreglo) ordenado de “n” elementos se trata de escribir una función que encuentre un elemento dado “x” y devolver la posición del array en la que se encuentra. Es decir, este método nos va a permitir localizar un elemento determinado dentro de una colección. Te vamos a mostrar varias soluciones del algoritmo de búsqueda binaria escrito en Java.
Un requisito fundamental en la búsqueda binaria es que el array o arreglo se encuentre ya ordenado. Por tanto, si el array no se encuentra ordenado primero tendremos que ejecutar un algoritmo de ordenación como Quicksort.
Pasemos a ver las soluciones y ejemplos.
Array de datos: datos[] = {11, 23, 30, 50, 60, 80, 115, 130, 140, 170}, x = 115
Salida: 6
El elemento x se encuentra en la posición 6 del array.
Array de datos: datos[] = {10, 20, 37, 40, 62, 111, 120, 131, 190}, x = 133
Salida: -1
El elemento x no se encuentra en el array.Pseudocódigo búsqueda binaria
Los pasos a seguir para ejecutar una búsqueda binaria son los siguientes:
- Iniciar con el elemento intermedio del array como clave.
- Si el valor de la clave es igual al elemento buscado entonces se devuelve el índice de la clave inicial.
- Si el valor de la clave es menor que el elemento buscado en mitad del intervalo, acotar el intervalo a la mitad más baja.
- Si no, acotar el intervalo a la mitad más alta.
- Repetir los pasos anteriores hasta que el intervalo quede vacío.
Implementación Algoritmo Iterativo
Esta solución propone un algoritmo de búsqueda binaria iterativo escrito en Java que implementa la búsqueda binaria sobre un array o arreglo ordenado:
class BusquedaBinaria{
int busquedaBinaria(int elementos[], int x)
{
int l = 0, r = elementos.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (elementos[m] == x)
return m;
if (elementos[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
public static void main(String args[])
{
BusquedaBinaria bb = new BusquedaBinaria();
int elementos[] = { 1, 2, 4, 10, 50 };
int n = elementos.length;
int x = 10;
int resultado = ob.binarySearch(elementos, x);
if (resultado == -1)
System.out.println("El elemento no esta presente");
else
System.out.println("Elemento encontrado en: "
+ "indice" + resultado);
}
}Implementación Algoritmo Recursivo
Solución del algoritmo de búsqueda binaria utilizando una función recursiva sobre un array:
class BusquedaBinaria {
int busquedaBinaria(int elementos[], int l, int r, int x)
{
if (r >= l) {
int mitad = l + (r - l) / 2;
if (elementos[mitad] == x)
return mitad;
if (elementos[mitad] > x)
return busquedaBinaria(elementos, l, mitad - 1, x);
return busquedaBinaria(elementos, mitad + 1, r, x);
}
return -1;
}
public static void main(String args[])
{
BusquedaBinaria bb = new BusquedaBinaria ();
int elementos[] = { 2, 3, 4, 10, 40 };
int n = elementos.length;
int x = 10;
int resultado = bb.busquedaBinaria(elementos, 0, n - 1, x);
if (resultado == -1)
System.out.println("No se ha encontrado el elementos buscado");
else
System.out.println("Elemento encontrado en la posicion: "
+ resultado );
}
}
Complejidad Búsqueda Binaria
Una aproximación para resolver el problema de búsqueda general es a través de un algoritmo de búsqueda lineal. La complejidad de este proceso sería O(n). Implementando un algoritmo de búsqueda binaria se optimiza la complejidad computacional a O(Log n).
Más algoritmos de búsqueda y ordenación
| Asunto | Descripción |
| Ordenación Burbuja | Ordenación algoritmo BubbleSort. |
| Ordenación Inserción | Algoritmo de ordenación por inserción |
| Ordenación Selección | Algoritmo de ordenación por selección |
| Ordenación Quicksort | Algoritmo de ordenación eficiente Quicksort |
| Búsqueda Binaria | Algoritmo de búsqueda binaria |
| Patrones: Algoritmo Z | Detección de patrones con algoritmo Z |
| Patrones: Algoritmo Naive | Detectar patrones con algoritmo ingenuo o naive |
| Algoritmo de Dijkstra | Como encontrar el camino más corto entre dos nodos en un grafo ponderado |
| Algoritmo de Kruskal | Se utiliza para encontrar el árbol de expansión mínimo en un grafo ponderado |
Recursos básicos Java
| Asunto | Descripción |
| Tutorial básico y sintaxis | Tutorial básico Java y sintaxis. Aprende los fundamentos del lenguaje. |
| Hilos (Threads) | Aprende a manejar hilos y las cuestiones básicas de la concurrencia |
| Funciones Lambda | Aquí te enseñamos las nociones más importantes para arrancas con funciones lambda |
| Palíndromos | Programa de ejemplo para el uso de palíndromos en Java. |
| Máquina Virtual de Java | Te explicamos el funcionamiento de la máquina virtual de java (Java Virtual Machine – JVM) |
| JDK, JRE y JVM | Diferencias entre el JDK, JRE y JVM. |
| Mejores libros Java en Español | Hazte con los mejores libros Java para aprender paso a paso y profundizar en las mejores prácticas |
| TensorFlow | Manejo del API de TensorFlow para la construcción de grafos de operaciones y su ejecución |
| Tutorial Log4j | Tutorial para el manejo de Log4j, herramienta ágil y flexible para la gestión de Logs en Java |
| Java Security | Entiende y aplica las posibilidades que da Java para mantener la seguridad |
| Tutorial JConsole | Aprende los conceptos básicos de monitorización de procesos Java con JConsole |
| JavaFX | Tutorial de JavaFX, librería gráfica moderna para construcción de GUIs en móvil, escritorio y web. |
| Estructuras de datos en Java | Explicación y ejemplos de las estructuras de datos más importantes: listas, pila, cola, arbol. |
| Javaapi | Conjunto de clases, interfaces, métodos y paquetes que forman parte de la plataforma Java estándar |
| Algoritmo Huffman | Método eficiente para codificar datos, asignando códigos más cortos a los caracteres más frecuentes |