Ordenamiento de datos: Búsqueda binaria en Java

Cuando tenemos que buscar un dato dentro de un arreglo de datos, uno de los métodos más eficaces de hacerlo es mediante el algoritmo de búsqueda binaria, capaz de encontrar un dato en arreglos de gran tamaño en tan sólo unos instantes, gracias a la poca cantidad de operaciones que realiza en memoria, siendo muy efectivo y consumiendo muy pocos recursos.

A continuación te mostraré como implementar este algoritmo de búsqueda en el lenguaje de programación Java.

Funcionamiento de la búsqueda binaria

El algoritmo de búsqueda binaria (también conocido como búsqueda dicotomica o búsqueda de bisección) requiere recibir un arreglo de datos ordenado, donde comprobará si el valor a la mitad del arreglo es igual al valor que se busca. Si esto se cumple, la búsqueda termina. Si, por el contrario, el valor de búsqueda es mayor al valor colocado en medio del arreglo, entonces se aplica de nuevo la busqueda binaria, pero esta vez sobre un nuevo arreglo que tomará como primer valor el punto medio del anterior arreglo. En el caso de que el valor de búsqueda sea menor al valor colocado en medio del arreglo, se aplica de nuevo la búsqueda binaria, pero sobre un nuevo arreglo que tomará como último valor el punto medio del arreglo anterior.

En resumen, se verifica si el valor buscado es igual al de la mitad del arreglo; si es igual, termina la búsqueda; si es mayor, se descarta el lado izquierdo del arreglo y se repite la búsqueda; si es menor, se descarta el lado derecho del arreglo y se repite la búsqueda.

En la siguiente animación puedes ver gráficamente el funcionamiento de la búsqueda binaria:

En la mayoría de los casos, la búsqueda binaria es uno de los métodos de búsqueda más rápidos que podemos implementar, ya que al ir reduciendo el área de búsqueda por la mitad con cada iteración, reduce el tamaño del problema logaritmicamente, por lo que se dice que su complejidad es de O(log n).

Búsqueda binaria en Java

En código de Java, podemos expresar el anterior algoritmo de forma recursiva así:

Para llamarlo más facilmente, podemos sobrecargar el método y definirlo con menos argumentos:

Alternativamente, podemos implementar una versión del mismo usando iteraciones en vez de recursividad:

Explicación del código paso a paso

Si tienes alguna duda respecto al código, a continuación te dejo una breve explicación de como funciona el código de la función de búsqueda binaria recursiva.

Básicamente, comenzamos declarando una función que reciba los siguientes parametros: arreglo donde se buscara un valor, valor a buscar, extremo inferior del arreglo (Indice donde comenzaremos a buscar) y extremo superior (Último indice donde buscaremos).

Después, obtenemos el índice de la posicion media del arreglo, promediando inf y sup

La primer condición if dice que si inf es mayor o igual a sup, y el valor del elemento es esa posición del arreglo no es igual al buscado, entonces el elemento no esta en el arreglo, y se regresa el valor -1. Esta condición sólo se alcanzará si la función recibe un arreglo de largo 1, lo que se puede dar al llegar al último llamado de la recursión cuando el arreglo no se pueda recortar mas.

La segunda condición marca que si el elemento de la mitad del arreglo es igual al valor buscado, entonces lo hemos encontrado, y se regresa el valor de la variable mitad, que contiene la posición donde se encuentra el elemento.

La siguiente parte del código expresa que, si el valor buscado es mayor al valor a la mitad del arreglo, se repita la búsqueda pero tomando en cuenta sólo la segunda mitad del arreglo. La última expresión, que se alcanza sólo si ninguna de las condiciones se cumple (Situación que se da cuando valor es menor al elemento a la mitad del arreglo), hace lo contrario: Repite la busqueda tomando en cuenta sólo la primera mitad del arreglo.

Al ser una función recursiva, el arreglo se irá recortando por la mitad con cada llamado a la función, por lo que requerirá de muy pocas operaciones para encontrar un valor.

Rendimiento del algoritmo

Como la búsqueda binaria divide un problema a la mitad cada vez que se ejecuta, su complejidad es de O (log n), una de las más efectivas que podemos encontrar en algoritmos. Podemos compararla con la búsqueda lineal, de complejidad O (n) y también muy utilizada por lo facil que puede expresarse en código.

Se toman los siguientes casos:

  • Valor presente al comienzo de un arreglo de 10 elementos
  • Valor presente en un arreglo de 100 elementos
  • Valor ausente en un arreglo de 10,000 elementos
  • Valor presente al final de un arreglo de 1,000,000 elementos
  • Valor presente al final de un arreglo de 10,000,000 elementos

*Nota: Cada prueba se realizo en un equipo con un procesador Intel Core i3 a 1,9 GHz.

Los resultados fueron los siguientes:

Búsqueda Binaria vs Búsqueda Lineal
N de Elementos Posicion del elemento Tiempo Busqueda Binaria (seg) Tiempo Busqueda Lineal (seg)
10 0 0.000009638 0.000002977
100 70 0.000001744 0.000005457
10000 N/A 5.26E-06 2.91E-04
1000000 999999 8.14E-06 0.006470215
10000000 9999999 7.11E-06 0.005461539

Si lo colocamos en una gráfica, podemos ver como, mientras crece el tamaño del arreglo, aumenta la diferencia entre el rendimiento de la búsqueda binaria y la búsqueda secuencial, siendo la primera mucho más rápida:

Para poder apreciar mejor la diferencia entre ambas, podemos desarrollar una gráfica logaritmica, donde queda patente como el algoritmo binario ofrece un tiempo de búsqueda más o menos constante, mientras la búsqueda secuencial sólo tarda más para encontrar un valor mientras crece el tamaño del arreglo.

Como puedes observar, al tener un arreglo de pocos elementos la búsqueda lineal es más veloz que la búsqueda binaria, pero esto cambia al aumentar el tamaño del arreglo, y para cuando llegamos al millón de elementos, la búsqueda binaria es más de 700 veces más rápida que la búsqueda secuencial.

Debes tomar en cuenta que estas pruebas son sólo para darnos una idea de la efectividad de la búsqueda secuencial, ya que pueden encontrarse algunas anomalías como que la búsqueda lineal tarde más en encontrar un valor en un arreglo con 1 millón de elementos que con 10 millones; aunque esto puede ser producto de las optimizaciones del compilador. En lenguajes interpretados, como Python, la diferencia entre algoritmos será mucho mayor.

Aquí puedes encontrar el código utilizado para realizar esta pequeña prueba.

Conclusión

La búsqueda binaria es un algoritmo simple y muy eficaz para encontrar elementos en un arreglo ordenado de datos.

Aunque actualmente los lenguajes de programación más utilizados de mas alto nivel como Python, Ruby o C# cuentan con métodos de búsqueda integrados muy optimizados, es útil conocer como implementar la búsqueda binaria para poder adaptar este algoritmo a tus necesidades, además de que podrás utilizarlo bajo cualquier entorno, sin importar si el lenguaje o entorno que tengas que utilizar cuente con las librerias donde se almacenen los métodos de búsqueda de dichos lenguajes.

Además, la búsqueda binaria, por su efectividad y simpleza, es una gran introducción al área de los algoritmos en lenguajes de programación; si te interesa aprender más sobre algoritmos y eficiencia computacional, te recomiendo que eches un vistazo a los siguientes libros:

 Algoritmos a Fondo – Amazon  Analisis de Algoritmos – Amazon Mastering Java 9 – Amazon

¿Qué otros métodos de búsqueda conoces? ¿Qué uso le has dado a la búsqueda binaria? ¡Espero tus comentarios!

Tags:

Share Post :

More Posts