En esta oportunidad vamos a resolver un algoritmo de búsqueda conocido como Binary search, usualmente se utiliza en los cursos de ciencias de la computación, ingeniería de sistemas o de software, también en carreras técnicas similares, es por esto que muchas veces el saber este algoritmo se da por sentado, pero no debería ser así.

Lo bueno viene cuando estás en alguna entrevista técnica y te pidan que lo desarrolles o en tu trabajo tengas la oportunidad de emplearlo, es entonces cuando te das cuenta que como desarrollador de software nunca debes dar por sentado tus conocimientos, sino más bien debes estar constantemente practicando y puliendo tus skills, en este caso tus skills duros es decir, técnicos.

Debes practicarlo tanto, que te sientas cómodo trabajando con algoritmos.

Ten en cuenta que la búsqueda binaria de un número en un arreglo se aplica a aquellos arreglos que están ordenados de forma ascendente.

Algoritmo

El enunciado para un binary search es el siguiente: Dado un arreglo de enteros ordenados, se pide devolver el índice de un número a buscar, en caso no esté en el arreglo retornar -1.

Aquí está el algoritmo en el lenguaje C#

        public static int Search(int[] arreglo, int x)
        {
            int left = 0; //extremo izquierdo de nuestra porción del arreglo a analizar
            int right = arreglo.Length - 1; //extremo derecho

            while (left <= right)
            {
                int middle = left + (right - left) / 2; //buscamos el punto medio

                if (arreglo[middle] == x)
                    return middle;

                if (x > arreglo[middle])
                    left = middle + 1;
                else
                    right = middle - 1;
            }
            return -1;
        }

Análisis

No es casualidad la imagen principal de esta entrada, el mapa de la chica está dividido en varias partes, haciéndolo más pequeño cada vez, de forma similar funciona este algoritmo.

En este algoritmo, como ya mencioné, se aplica cuando el arreglo se encuentra ordenado, ya que se basa en la siguiente práctica: "Divide y vencerás".

El algoritmo calcula el elemento medio del arreglo, partiendo así el array en dos partes.

Compara si el número buscado es el central, si es así, devuelve su índice.

Si el número buscado es mayor, entonces recalcula los extremos izquierdo y derecho, lo mismo ocurre si el número es menor que el central. Esto es posible ya que asumimos que el arreglo está ordenado.

Repetimos estos pasos hasta acorralar al número buscado y devolver su índice, en caso no existe devolvemos -1.

Análisis de Complejidad temporal

¿Qué es eso dirás tú?

En esta entrada previa, está todo lo que tienes que saber de este tema. Te recomiendo leero y ponerlo en práctica. Pero aquí un resumen: Time complexity o complejidad temporal es una notación (Big-O notation) de la cantidad de tiempo que llevará ejecutar un algoritmo pudiendo ser lineal, logarítmico, exponencial, etc.

Como podemos ver, esta técnica de búsqueda va haciendo cortes al arreglo, como dije antes, hace un "divide y vencerás" partiendo a la mitad al arreglo y así sucesivamente hasta dar con el número buscado, es por esto que tiene una complejidad temporal de O(Log n) ya que las iteraciones no avanzan de 1 en 1 sino en múltiplos de 2.

Sólo un datito, la búsqueda normal donde iteramos por cada elemento comparando uno por uno es llamada búsqueda lineal y su complejidad temporal al iterar por cada elemento hasta hallar el indicado es de O(n).

Así es que crack! ya sabes un algoritmo más, y también aprendiste un poco eso del time complexity, son temas que aunque creas que no los usarás en la práctica, déjame decirte que sí te ayudarán en tu día a día, aprender algoritmos es como calistenia para el cerebro de un developer, practícalos y sé un bravo de bravos.

Recuerda que esta entrada es de la serie de artículos Algoritmos notables, los cuales los subo a este repo, puedes visitarlo y descubrir más algoritmos 😊

Si te ha fascinado, pero fascinado mucho esta entrada compártela ☺