Búsqueda binaria en Java paso a paso

El algoritmo de búsqueda binaria funciona sobre arreglos ordenados y es utilizado para buscar un elemento en los mismos.

Funcionamiento

El funcionamiento del algoritmo es simple y cuenta con las siguientes partes:

  • Datos de entrada :
    • Un arreglo ordenado
    • Un valor a buscar en el arreglo
  • Datos de salida:
    • La posición del elemento en el arreglo o -1 en caso de no encontrarlo

El algoritmo de búsqueda binaria sigue los siguientes pasos:

  • Verifica si el elemento a buscar es menor al máximo elemento en el arreglo y mayor al mínimo elemento del arreglo, en caso de no ser así  se devolverá -1 ya que sabemos que no se encuentra el elemento.
  • Obtiene el elemento que se encuentra en la mitad del arreglo y lo compara con el valor que se busca.
  • En caso de que el elemento sea mayor al valor que se busca se descartará la parte derecha y se volverá a ejecutar la misma validación pero solo sobre el lado izquierdo del arreglo.
  • El paso anterior se repetirá hasta encontrar el elemento
  • En caso de no encontrar el elemento se devolverá -1 para indicar que no se encontró.

Ejemplo práctico

A continuación presentaremos un ejemplo paso a paso de la búsqueda binaria, imaginemos el siguiente arreglo donde se desea buscar el número 400:

paso1

  • Evaluar que el número 400 es mayor al menor elemento del arreglo y menor al máximo elemento del arreglo, en este caso 10 es menor y 2222 es mayor a 400, entonces podemos pasar al siguiente paso.
  • Obtendremos el elemento de la mitad del arreglo utilizando la siguiente ecuación (límite inferior + límite superior)/2
  • En este caso la mitad del arreglo es 120, una vez hecho esto evaluaremos si 120 es mayor o menor al número que buscamos, que en este caso es 400, 400 es mayor a 120, esto significa que se encuentra del lado derecho del arreglo, así que el lado izquierdo será descartado como se muestra en la siguiente imagen:

paso2

  • Una vez hecho esto volveremos a dividir el arreglo, pero en este caso nuestro límite inferior no será 10 sino ahora será 200, y el nuevo valor de en medio será 500 como se muestra en la siguiente imagen:

paso3

  • Una vez más evaluaremos si el número 500 es mayor o menor al número que buscamos que es 400, en este caso 400 es menor a 500, entonces la parte de la derecha será descartada como se muestra en la siguiente imagen:

paso4

  • Con lo anterior el nuevo límite inferior es el 200 y el nuevo límite superior es 400 así que ejecutaremos nuestra ecuación para obtener el elemento de la mitad, en este caso es la posición 7 del arreglo que es 200 así que volveremos a reducir en uno el límite superior, con esto tanto el límite superior como el límite inferior se encuentran en la posición 8 como se muestra en la siguiente imagen:

paso 5

  • Listo ! encontramos el elemento que buscábamos en el arreglo, esto nos tomó 4 iteraciones en lugar de 9 si hubiéramos iterado el arreglo indice por indice, con esto se demuestra que es mucho más eficiente que iterar el arreglo posición por posición. La complejidad de una búsqueda lineal es de O(n) mientras que la complejidad de una búsqueda binaria es O(Log n) lo cuál indica que es mucho más eficiente, solo consideremos que para poder ejecutarla el arreglo debe estar ordenado.

Implementación de la búsqueda binaria en Java

A continuación se presenta el código para ejecutar la búsqueda binaria en Java:

public class ChallengeClass {
	public static int binarySearch(int[] array, int minLimit, int maxLimit, int value) {
		if (maxLimit >= 0 && array[minLimit] <= value && array[maxLimit] >= value) {
			int mid = getMidValue(minLimit, maxLimit);
			System.out.println(String.format("Límite inferior %d límite superior %d valor en el arreglo %d valor a buscar %d", minLimit,maxLimit,array[mid],value));
			if (array[mid] == value) {
				return mid;
			} else if (array[mid] <span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>< value) {
				return binarySearch(array, mid + 1, maxLimit, value);
			}
			return binarySearch(array, minLimit, mid - 1, value);
		}
		return -1;
	}

	public static int getMidValue(int minLimit, int maxLimit) {
		return (maxLimit + minLimit) / 2;
	}

	public static void main(String[] args) {
		int value = 400;
		int[] array = { 10, 15, 20, 40, 50, 100, 120, 200, 400, 500, 600, 800 ,2222};
		int result = binarySearch(array, 0, array.length - 1, value);
		System.out.println(String.format("Result %d", result));
	}
}

La implementación presentada fue hecha sin utilizar ningún api de Java para el manejo de búsquedas u ordenamientos.

Implementación de búsqueda binaria utilizando clases existentes en Java

Como sabemos Java provee de un framework para el manejo de colecciones y arreglos, a continuación se presenta el código para ejecutar la búsqueda binaria utilizando dichas clases:

import java.util.Arrays;

public class ChallengeClass {

	public static void main(String[] args) {
		int[] array = { 10, 15, 20, 40, 50, 100, 120, 200, 400, 500, 600, 800, 2222 };
		int result = Arrays.binarySearch(array, 400);
		System.out.println(String.format("Result %d", result));
	}
}

Es importante mencionar que el método binarySearch de la clase Arrays también requiere que el arreglo que se pase como parámetro se encuentre ordenado, en caso contrario los resultados pueden ser erróneos.

Si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s