Hoy vamos a ver cómo aplicar la búsqueda binaria para buscar elementos en arreglos usando el lenguaje de programación C# también conocido como C sharp.

Te voy a mostrar dos métodos: uno para hacer la búsqueda binaria (divide y vencerás) usando recursividad y otro método usando el ciclo while.

Al final tendremos dos funciones que nos permitirán buscar un elemento en un array usando el algoritmo de la búsqueda binaria.

Sobre la búsqueda binaria

Recuerda que el arreglo al que vamos a aplicar esta búsqueda (contrario a la búsqueda secuencial en donde no importa) debe estar ordenado.

Esta búsqueda utiliza el enfoque de divide y vencerás. Primero tomamos el elemento central que está entre nuestros límites y comparamos para ver si es lo que buscamos, en caso de que sí, regresamos el índice.

En caso de no encontrarlo entonces comparamos si el elemento central es menor o mayor al que buscamos. Si es menor entonces dividimos el arreglo desde el centro a la izquierda, y si es mayor, lo dividimos desde el centro a la derecha.

Esto ya lo expliqué más a fondo en un post dedicado a ello. Si te interesa profundizar, léelo aquí.

Búsqueda binaria en C# con recursión

Veamos el primer método de este programa en C# aplicando la recursividad. Vamos a implementar la búsqueda binaria, para ello necesitamos definir una función que recibirá:

1. El arreglo
2. La búsqueda
3. El índice izquierdo
4. El índice derecho

Y queda así:

See the gist on github.

La condición de salida es que la izquierda supere a la derecha, ya que en ese caso habremos acabado de recorrer el arreglo; lo que significa que el elemento buscado no existe.

Después de eso hacemos la comparación. La aplicación del Divide y vencerás está en la línea 19 y línea 24, pues modificamos los límites y volvemos a invocar a la función (aplicando recursión).

La función nos va a devolver -1 o el índice del arreglo en donde se encuentra el elemento buscado.

Nota: en los modos de uso te enseñaré cómo invocar a la función por primera vez.

Búsqueda binaria con ciclo while en C#

Ahora veamos el enfoque con ciclos o loops. Básicamente es el mismo algoritmo en donde modificamos los límites pero ahora lo hacemos dentro del ciclo. Queda así:

See the gist on github.

Fíjate que en este caso la función no recibe la izquierda y derecha, pues no los necesitamos porque no vamos a volver a invocar a la función dentro de sí misma.

Modo de uso

Ya te mostré las dos funciones. Esto fue con enteros pero igualmente funcionaría con cadenas, solo hay que comparar correctamente.

En fin, el modo de uso es el siguiente:

See the gist on github.

En la línea 3 declaro mi arreglo, después lo ordeno en la línea 6. Obviamente tú puedes usar cualquier método para ordenarlo, yo he usado ese por simplicidad.

Después en la línea 7 imprimo el arreglo para mostrar su estructura. Finalmente invoco a la función de búsqueda binaria en la línea 16, misma que me va a devolver un índice.

Nota: en el ejemplo estoy invocando a busquedaBinaria pero igualmente podrías invocar a busquedaBinariaWhile como se indica en el comentario. Fíjate que al inicio los límites del arreglo son 0 para la izquierda y la longitud del arreglo menos uno para la derecha.

Finalmente imprimo si el elemento fue encontrado o no, así como la posición del mismo.

Poniendo todo junto

El código completo en mi caso (por si quieres verlo todo) queda así:

See the gist on github.

Y como siempre, te dejo aquí un enlace para que lo pruebes en vivo. Si C sharp o C# te gusta, te invito a leer más entradas sobre este lenguaje en mi blog.