Exploramos en profundidad el Algoritmo de Búsqueda Binaria en Java

En esta entrada exploramos en profundidad el algoritmo de Búsqueda Binaria en Java. Primero realizaremos una explicación en detalle de como funciona el algoritmo, para posteriormente realizar diferentes implementaciones en Java del mismo y por último, realizar pruebas sobre estas implementaciones.

¿ Qué vamos a ver en este post ?

1. Introducción. Una introducción donde explicaremos el funcionamiento del algoritmo con todo lujo de detalles.
2. Su implementación en Java para Arrays de enteros.
3. Su implementación en Java para Arrays de clases Productos.
4. Su implementación en Java para Arrays de tipos de datos genéricos utilizando «templates».

Vamos al lio!!!

Introducción

El algoritmo de «búsqueda binaria» es un tipo de algoritmo de búsqueda de elementos extremadamente eficiente para grandes conjuntos de datos debido a que su orden de complejidad en el peor de los casos es logarítmico.

Mediante este algoritmo podemos encontrar elementos en un conjunto de datos de una forma muy eficiente.

¿ Cómo funciona ?

Para explicar el funcionamiento del algoritmo partiremos de las siguientes bases:

1. Tendremos una lista de enteros. es decir, un Array de memoria estática de 10 elementos.
2. Los elementos de nuestra lista de enteros estarán ordenados. Esta condición es indispensable para que el algoritmo pueda funcionar correctamente.

Por lo tanto, partimos de la siguiente base:

Como podéis apreciar son 10 elementos de tipo entero ordenados de manera ascendente.

Vamos a suponer que buscamos el elemento 45, nuestro algoritmo necesitará 3 variables de control:

1. Una variable llamada «limiteInferior». Esta variable la utilizaremos para delimitar desde que elementos empezamos a buscar empezando por el valor 0. En cada iteración el valor de esta variable puede cambiar.
2. Una variable llamada «limiteSuperior». Esta variable la utilizaremos para delimitar desde que elementos empezamos a buscar empezando por el valor número de elementos -1. En cada iteración el valor de esta variable puede cambiar.
3. Una variable llamada «indice». Esta variable será el elemento que buscaremos en cada iteración. Sí, se trata de un algoritmo iterativo. En cada iteración el valor de esta variable cambiará.

La primera iteración

En la primera iteración realizaremos las siguientes acciones:

1. Seleccionaremos como «limiteInferior» la posición 0 de nuestro Array.
2. Seleccionaremos como «limiteSuperior» la última posición de nuestro Array. En este caso 9
3. Calcularemos el valor de nuestra variable índice. «indice» = («limiteInferior» + «limiteSuperior») / 2. En este caso (0 + 9) / 2 = 4.5, al ser un entero se redondea a 4.

Tendríamos la siguiente representación:

¿ Qué realiza nuestro algoritmo en la primera iteración ?

Nuestro algoritmo en la primera iteración realiza los siguientes pasos:

1. Comprueba si «v[indice]» es igual al elemento buscado. Recordad que estamos buscando el elemento «45».
2. Como «v[4]» tiene un valor de «57», nuestro número en caso de estar en nuestro Array tiene que estar hacia la izquierda de «v[4]» porque «v[4]=57» es mayor que «45». Cambiamos el valor del «límiteSuperior» al valor de «indice» de la iteración anterior restando 1. En este caso 4 -1 = 3.
3. Límite inferior se queda como está.
4. Realizamos la segunda iteración.

La segunda iteración

La representación sería la siguiente:

¿ Qué realiza nuestro algoritmo en la segunda iteración ?

En la segunda iteración realizamos los mismos pasos que en la primera iteración pero con los valores que tenemos en esta iteración:

1. Calcularemos el valor de nuestra variable índice. «indice» = («limiteInferior» + «limiteSuperior») / 2. En este caso (0+ 3) / 2 = 1.5, al ser un entero se redondea a 1.
2. Comprueba si «v[indice]» es igual al elemento buscado. Recordad que estamos buscando el elemento «45».
3. Como «v[1]» tiene un valor de «33», nuestro número en caso de estar en nuestro Array tiene que estar hacia la derecha de «v[1]» porque «45» es mayor que «v[1]=33». Cambiamos el valor del «limiteInferior» al valor de «indice» de la iteración anterior sumando 1. En este caso 1 + 1 = 2.
4. «limiteSuperior» se queda como está, en 3.
5. Realizamos la tercera iteración.

La tercera iteración:

La representación sería la siguiente:

¿ Qué realiza nuestro algoritmo en la tercera iteración ?

En la tercera iteración realizamos los mismos pasos que en las iteraciones anteriores. Pero en esta iteración ya vamos a encontrar el elemento buscado.

1. Calcularemos el valor de nuestra variable índice. «indice» = («limiteInferior» + «limiteSuperior») / 2. En este caso (2 + 3) / 2 = 2.5, al ser un entero se redondea a 2.
2. Comprueba si «v[indice]» es igual al elemento buscado. Recordad que estamos buscando el elemento «45». En este caso «v[indice]», que es «v[2]» tiene un valor de «45», que es el número que estamos buscando, por lo tanto, aquí acaba nuestro algoritmo.

Vamos a buscar un número que no existe

Vamos a realizar la traza de otro ejemplo, en este caso con un número que no existe, vamos a buscar el número «58»

En la primera iteración partimos de la misma base que en el ejemplo anterior.

La primera iteración

¿ Qué realiza nuestro algoritmo en la primera iteración ?

Nuestro algoritmo en la primera iteración realiza los siguiente:

1. Calcularemos el valor de nuestra variable índice. «indice» = («limiteInferior» + «limiteSuperior») / 2. En este caso (0 + 9) / 2 = 4.5, al ser un entero se redondea a 4.
2. Comprueba si «v[indice]» es igual al elemento buscado. Recordad que estamos buscando el elemento «58».
3. Como «v[4]» tiene un valor de «57», nuestro número en caso de estar en nuestro Array tiene que estar hacia la derecha de «v[4]» porque «v[4]=57» es menor que «58». Cambiamos el valor del «limiteInferior» al valor de «indice» de la iteración anterior sumando 1. En este caso 4 + 1 = 5.
4. «limiteSuperior» se queda como está, en 9.
5. Realizamos la segunda iteración.

La segunda iteración

La representación sería la siguiente:

¿ Qué realiza nuestro algoritmo en la segunda iteración ?

Nuestro algoritmo en la segunda iteración realiza los siguiente:

1. Calcularemos el valor de nuestra variable índice. «indice» = («limiteInferior» + «limiteSuperior») / 2. En este caso (5 + 9) / 2 = 7.
2. Comprueba si «v[indice]» es igual al elemento buscado. Recordad que estamos buscando el elemento «58».
3. Como «v[7]» tiene un valor de «93», nuestro número en caso de estar en nuestro Array tiene que estar hacia la izquierda de «v[7]» porque «v[7]=93» es mayor que «58». Cambiamos el valor del «limiteSuperior» al valor de «indice» de la iteración anterior restando 1. En este caso 7 – 1 = 6.
4. «limiteInferior» se queda como está, en 5.
5. Realizamos la tercera iteración.

La tercera iteración

¿ Qué realiza nuestro algoritmo en la tercera iteración ?

Nuestro algoritmo en la tercera iteración realiza lo siguiente:

1. Calcularemos el valor de nuestra variable índice. «indice» = («limiteInferior» + «limiteSuperior») / 2. En este caso (5 + 6) / 2 = 5.5, que se redondea a 5.
2. Comprueba si «v[indice]» es igual al elemento buscado. Recordad que estamos buscando el elemento «58».
3. Como «v[5]» tiene un valor de «87», nuestro número en caso de estar en nuestro Array tiene que estar hacia la izquierda de «v[5]» porque «v[5]=87» es mayor que «58». Cambiamos el valor del «limiteSuperior» al valor de «indice» de la iteración anterior restando 1. En este caso 5 – 1 = 4.
4. «limiteInferior» se queda como está, en 5.
5. Realizamos la tercera iteración.

La cuarta y última iteración

La representación sería la siguiente:

Como hemos cruzado los índices se acaba nuestro algoritmo, y podemos concluir que el número que estamos buscando no existe.

Implementación de la Búsqueda Binaria en Java

En esta sección vamos a implementar el algoritmo en Java, lo haremos en varias iteraciones, haciéndolo cada vez más genérico. Realizaremos las siguientes implementaciones:

1. Una primera implementación que buscará un determinado número en un Array de enteros «int».
2. Una segunda implementación que buscará un determinado «producto» en un Array de «Productos».
3. Una tercera implementación que servirá para realizar una búsqueda binaria sobre cualquier objeto y sobre cualquier tipo de atributo.

Para cada implementación de las comentadas anteriormente realizaremos pruebas sobre determinadas búsquedas. Vamos al lio con la primera implementación.

Búsqueda Binaria sobre un Array de enteros

Nuestro algoritmo sería el siguiente:

public static int busquedaBinaria(int [] items, int numeroBuscado) {
	int result = -1;
	int limiteInferior = 0;
	int limiteSuperior = items.length - 1;
	int indice;
				
	while (limiteInferior <= limiteSuperior && result == -1) {
		indice = (limiteInferior + limiteSuperior) / 2;
			
		if (items[indice] == numeroBuscado) {
			System.out.println("Encontrado");
			result = indice;
		}else if (numeroBuscado > items[indice]) {
			limiteInferior = indice + 1;
		}else if (numeroBuscado < items[indice]) {
			limiteSuperior = indice - 1;
		}
	}
		
	return result;
}

Explicación del algoritmo de Búsqueda Binaria

Nuestro algoritmo funciona tal y como hemos descrito en la sección anterior. Repasemos ahora su implementación en Java.

1. El primer paso es crear las variables que necesitará nuestro algoritmo:
   1. La variable «result» inicializada a «-1». Servirá para devolver el índice del elemento buscado en caso de encontrarlo o «-1» en caso contrario.
   2. La variable que marcará el límite inferior. Se inicializa a 0.
   3. La variable que marcará el limite superior. Se inicializa al número de elementos -1.
   4. La variable que marcará nuestro «indice».
2. Bucle while, cuyas condiciones de parada son que se haya encontrado el número o que se hayan cruzado los índices.
3. La lógica dentro del bucle es:
   1. Se calcula el valor de «indice»
   2. Si «items[indice]» es igual al número buscado ya hemos encontrado el número y por lo tanto acaba nuestro algoritmo.
   3. Si el número buscado es > que «items[indice]», modificamos el límite inferior con el valor de «indice» +1.
   4. Si el número buscado es < que «items[indice]», modificamos el limite superior con el valor de «indice» – 1.
4. Por último devolvemos el resultado de nuestro algoritmo.

Pruebas de nuestro algoritmo

Veamos nuestro código

//Declaramos un Array de enteros con 20 posiciones
int [] misNumeros = new int[20];
		
//Asignamos 20 valores en nuestro Array
misNumeros[0] = 10;
misNumeros[1] = 13;
misNumeros[2] = 16;
misNumeros[3] = 19;
misNumeros[4] = 22;
misNumeros[5] = 25;
misNumeros[6] = 28;
misNumeros[7] = 31;
misNumeros[8] = 34;
misNumeros[9] = 37;
misNumeros[10] = 40;
misNumeros[11] = 43;
misNumeros[12] = 46;
misNumeros[13] = 49;
misNumeros[14] = 52;
misNumeros[15] = 55;
misNumeros[16] = 58;
misNumeros[17] = 61;
misNumeros[18] = 64;
misNumeros[19] = 67;
		
//Realizamos nuestras pruebas
int resultado = busquedaBinaria(misNumeros, 37);
System.out.println("El número 37 está en la posición: " + resultado);
resultado = busquedaBinaria(misNumeros, 70);
System.out.println("El número 70 está en la posición: " + resultado);

¿ Cuál es la salida de nuestro algoritmo ?

El número 37 está en la posición: 9
El número 70 está en la posición: -1

Búsqueda Binaria sobre un Array de Productos

Nuestro algoritmo sería el siguiente:

public static int busquedaBinariaClase(Producto [] items, int numeroBuscado) {
	int result = -1;
	int limiteInferior = 0;
	int limiteSuperior = items.length - 1;
	int indice;
				
	while (limiteInferior <= limiteSuperior && result == -1) {
		indice = (limiteInferior + limiteSuperior) / 2;
			
		if (items[indice].getId() == numeroBuscado) {
			System.out.println("Encontrado");
			result = indice;
		}else if (numeroBuscado > items[indice].getId()) {
			limiteInferior = indice + 1;
		}else if (numeroBuscado < items[indice].getId()) {
			limiteSuperior = indice - 1;
		}
			
	}
		
	return result;
}

Nuestra clase Producto

public class Producto{
	private int id;
	private String nombre;
		
	public Producto(int id, String nombre) {
		this.id = id;
		this.nombre = nombre;
	}
		
		
	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getNombre() {
		return nombre;
	}

	public void setNombre(String nombre) {
		this.nombre = nombre;
	}
}

Pruebas de nuestro algoritmo

//Creamos el Array de productos
Producto [] productos = new Producto[10];
		
//Insertamos los productos
productos[0] = new Producto(10);
productos[1] = new Producto(13);
productos[2] = new Producto(16);
productos[3] = new Producto(19);
productos[4] = new Producto(22);
productos[5] = new Producto(25);
productos[6] = new Producto(28);
productos[7] = new Producto(31);
productos[8] = new Producto(34);
productos[9] = new Producto(37);
	
//Buscamos un número que existe y un número que no existe
System.out.println("El producto con id 31 está en la posicion: " + busquedaBinariaClase(productos, 31));
System.out.println("El producto con id 899 está en la posicion: " + busquedaBinariaClase(productos, 899));

¿ Cuál es la salida de nuestro algoritmo ?

El producto con id 31 está en la posicion: 7
El producto con id 899 está en la posicion: -1

¿ Qué problemas existen en las implementaciones anteriores de Búsqueda Binaria ?

Uno de los problemas que surge inmediatamente después de ver los 2 algoritmos anteriores de «Búsqueda binaria» es que es necesario realizar una implementación diferente por cada tipo de elemento que tengamos en nuestro Array.

1. Hemos tenido que realizar una implementación para Arrays de «int».
2. Hemos tenido que realizar una implementación para objetos de la clase «Producto».

¿ Podemos solucionar este problema para realizar un único algoritmo de Búsqueda Binaria que sirva para cualquier tipo de objeto y para comparar por cualquier tipo de atributo de dicho objeto ?

Sí, claro que podemos, utilizando parametrización «E» e «Interfaces» en Java.

Vamos a ir transformando nuestro algoritmo para hacerlo genérico, veamos primero el algoritmo y luego veremos su explicación:

public static <E> int busquedaBinariaGenerica(TipoGenerico<E> [] items, E parametroBuscado) {
	int result = -1;
	int limiteInferior = 0;
	int limiteSuperior = items.length - 1;
	int indice;
				
	while (limiteInferior <= limiteSuperior && result == -1) {
		indice = (limiteInferior + limiteSuperior) / 2;
			
		if (items[indice].compare(parametroBuscado) == 0) {
			System.out.println("Encontrado");
			result = indice;
		}else if (items[indice].compare(parametroBuscado) == 1) {
			limiteInferior = indice + 1;
		}else if (items[indice].compare(parametroBuscado) == -1) {
			limiteSuperior = indice - 1;
		}
			
	}
		
	return result;
}

Lo primero en lo que nos tenemos que fijar es en que ahora el tipo de datos del Array de entrada por parámetro es del tipo de clase «TipoGenerico<E>», esto nos permitirá pasar cualquier tipo de Array, y que nuestro segundo parámetro, es decir, el elemento que buscamos también podrá ser parametrizable.

public static <E> int busquedaBinariaGenerica(TipoGenerico<E> [] items, E parametroBuscado)

¿ Pero qué es TipoGenerico<E> ?

TipoGenerico<E> es una simple «interface», cuyo código podemos ver a continuación:

public interface TipoGenerico<E> {
	public int compare(E elementoAComparar);
}

Esta «interface» obliga que toda clase que implemente dicha «interface» tenga que implementar el método «compare». El método compare devolverá:

• «0» sí el elemento que estamos buscando es igual al actual.
• «1» si el elemento que estamos buscando es > que el actual.
• «-1» si el elemento que estamos buscando es < que el actual.

Fijaos que el método «compare» también puede recibir cualquier tipo de parámetro de entrada:

public int compare(E elementoAComparar);

¿ Pero y cómo se utiliza todo esto ?

Vamos a ver nuestra clase producto, implementando la «interface» «TipoGenerico<Integer>»:

public class Producto implements TipoGenerico<Integer>{
	private int id;
	private String nombre;
		
	public Producto(int id, String nombre) {
		this.id = id;
		this.nombre = nombre;
	}
		
	public int compare(Integer elementoAComparar) {
		int result = -2;
			
		if (elementoAComparar == this.id) {
			result = 0;
		}else if (elementoAComparar > this.id) {
			result = 1;
		}else if (elementoAComparar < this.id) {
			result = -1;
		}
			
		return result;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getNombre() {
		return nombre;
	}

	public void setNombre(String nombre) {
		this.nombre = nombre;
	}
}

¿ Qué nos interesa de esta clase ?

Tenemos que fijarnos en 2 cosas principalmente, en cómo implementa la «interface» y en cómo implementa el método «compare»

public class Producto implements TipoGenerico<Integer>

public int compare(Integer elementoAComparar) {
	int result = -2;
			
	if (elementoAComparar == this.id) {
		result = 0;
	}else if (elementoAComparar > this.id) {
		result = 1;
	}else if (elementoAComparar < this.id) {
		result = -1;
	}
			
	return result;
}

Veamos un ejemplo buscando productos por un id «Integer» con nuestro método genérico

//Creamos el Array de productos
Producto [] productos = new Producto[10];
		
//Insertamos los productos
productos[0] = new Producto(10, "Abaco");
productos[1] = new Producto(13, "Balón");
productos[2] = new Producto(16, "Calcetin");
productos[3] = new Producto(19, "Dado");
productos[4] = new Producto(22, "Estantería");
productos[5] = new Producto(25, "Foco");
productos[6] = new Producto(28, "Grifo");
productos[7] = new Producto(31, "Huevo");
productos[8] = new Producto(34, "Item");
productos[9] = new Producto(37, "Juego de mesa");
	
//Buscamos un número que existe y un número que no existe
System.out.println("El producto con id 31 está en la posicion: " + busquedaBinariaGenerica(productos, 31));
System.out.println("El producto con id 899 está en la posicion: " + busquedaBinariaGenerica(productos, 899));

La salida de nuestro programa:

El producto con id 31 está en la posicion: 7
El producto con id 899 está en la posicion: -1

Veamos un ejemplo buscando productos por un su nombre «String» con nuestro método genérico

Para ellos tenemos que cambiar nuestra clase Producto, 2 pequeños cambios que veremos a continuación:

public class Producto implements TipoGenerico<String>{
		private int id;
		private String nombre;
		
		public Producto(int id, String nombre) {
			this.id = id;
			this.nombre = nombre;
		}
		
		public int compare(String elementoAComparar) {
			int result = -2;
			
			if (elementoAComparar.equals(this.nombre)) {
				result = 0;
			}else if (elementoAComparar.compareTo(this.nombre) > 0) {
				result = 1;
			}else if (elementoAComparar.compareTo(this.nombre) < 0) {
				result = -1;
			}
			
			return result;
		}

		public int getId() {
			return id;
		}

		public void setId(int id) {
			this.id = id;
		}

		public String getNombre() {
			return nombre;
		}

		public void setNombre(String nombre) {
			this.nombre = nombre;
		}
	}

1. Cambiamos el tipo en la «interface». public class Producto implements TipoGenerico<String>
2. Cambiamos el método «compare» para que sea compatible con «Strings».

Realizamos la llamada a nuestro método con un producto que existe y otro que no existe:

//Buscamos un número que existe y un número que no existe
System.out.println("El producto con nombre Grifo está en la posicion: " + busquedaBinariaGenerica(productos, "Grifo"));
System.out.println("El producto con nombre Regla está en la posicion: " + busquedaBinariaGenerica(productos, "Regla"));

La salida de nuestro programa:

El producto con nombre Grifo está en la posicion: 6
El producto con nombre Regla está en la posicion: -1

Por lo tanto, recopilando todo lo que hemos visto en este artículo. Hemos visto la explicación y 2 trazas del algoritmo de «búsqueda binaria», una implementación para enteros, una implementación para Productos buscando por su id, y una implementación totalmente genérica que sirve para cualquier tipo de «objeto» y cualquier tipo de «atributo», la cual hemos probado con «Integers» y «Strings».

Os dejo aquí los enlaces de todas las clases utilizadas:

Si os ha gustado este artículo de «Exploramos en profundidad el algoritmo de Búsqueda Binaria en Java» dejad un comentario en la lista de comentarios para apoyar el blog y si no habéis entendido algo también, así podré contestar vuestro comentario.

Si queréis profundizar más sobre el tema os dejo el siguiente enlace de Wikipedia.