Introducción

Veamos la implementación de un algoritmo que me gusta mucho; se trata de la búsqueda binaria. La primera vez que escuché de él fue en mi clase de Estructura de datos; ni siquiera sabía que algo así existía.

En fin, después de ello me fascinó mucho; sobre todo por la velocidad del mismo. Enseñaré cómo buscar una cadena en un arreglo usando recursividad con una búsqueda binaria, y cómo hacer lo mismo pero en un arreglo con números.

Haremos lo mismo pero usando el ciclo while; a eso se le llama búsqueda binaria en forma secuencial.

Nota: recuerda que este algoritmo requiere que el arreglo esté ordenado. Pásate por mi post para saber cómo ordenar arreglos de PHP.

Por otro lado, te recomiendo leer lo que son los argumentos que son tomados por referencia. Para redondear y calcular la mitad del arreglo usamos la función floor en PHP.

En caso de que obtengas errores de sintaxis con los corchetes es debido a la notación corta de arreglos en PHP.

Búsqueda binaria en arreglo de números usando recursividad en PHP

Me he dado a la tarea de poner todo esto en una función. Pongo aquí el código y más tarde lo explico:

<?php
/**
 *
 * Implementación del algoritmo de búsqueda binaria recursiva en un arreglo
 * usando PHP
 * Nota: este método sólo funciona con números
 *
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */
 
function busquedaBinariaRecursiva(&$arreglo, $busqueda, $izquierda, $derecha)
{
 
    /*
    Comprobar si ya no podemos partir el arreglo
     */
    if ($izquierda > $derecha) {
        return -1;
    }
    # Obtener el valor y elemento de la mitad del arreglo
    $indiceDelElementoMedio = floor(($izquierda + $derecha) / 2);
    $elementoDelMedio = $arreglo[$indiceDelElementoMedio];
 
    # ¿Lo que buscamos está en la mitad del arreglo? entonces regresa el índice
    if ($busqueda === $elementoDelMedio) {
        return $indiceDelElementoMedio;
    } else {
        # Si no, partimos el arreglo dependiendo de la búsqueda
        if ($busqueda > $elementoDelMedio) {
            # Si está a la derecha, lo partimos desde el medio + 1 hasta el elemento dado por derecha
            $izquierda = $indiceDelElementoMedio + 1;
            return busquedaBinariaRecursiva($arreglo, $busqueda, $izquierda, $derecha);
        } else {
            # Si está a la izquierda, lo partimos desde el medio - 1 hasta el elemento dado por izquierda
            $derecha = $indiceDelElementoMedio - 1;
            return busquedaBinariaRecursiva($arreglo, $busqueda, $izquierda, $derecha);
        }
    }
}

Lo que hacemos es mandar todo el arreglo, y no le hacemos ninguna operación; simplemente modificamos los índices o límites inferiores y superiores.

Es importante notar que el arreglo se pasa por referencia, ahorrando copiarlo en memoria cada que la función se llama.

Para partir el arreglo simplemente modificamos los índices, cuando lo partimos hacia la izquierda tomamos desde el punto medio -1 hasta el valor que tiene la izquierda. Y cuando lo partimos hacia la derecha tomamos el punto medio + 1 hasta el valor que tiene la derecha.

Llamada a la función

Para llamarla la primera vez, le pasamos los límites inferiores y superiores del arreglo, el arreglo y la búsqueda. La izquierda es el 0, y la derecha es la longitud del arreglo  – 1 (esto es porque los arreglos empiezan a tomar las posiciones en el 0).

Aquí el ejemplo:

<?php
$arreglo = [1, 5, 40, 45, 58, 77, 80, 200, 250];
$busqueda = 200;
$izquierda = 0;
$derecha = count($arreglo) - 1;
$indice = busquedaBinariaRecursiva($arreglo, $busqueda, $izquierda, $derecha);
echo "El elemento $busqueda está en el índice $indice";

La salida es:

El elemento 200 está en el índice 7

Si lo que buscamos no está, se devuelve -1.

Búsqueda binaria en arreglo de números usando el ciclo while en PHP

Es lo mismo de arriba pero ahora no usamos recursividad, sino un ciclo while que se ejecutará siempre y cuando la derecha o el límite superior sea mayor o igual que la izquierda.

Igualmente está dentro de una función, pero dicha función ahora recibe únicamente el arreglo y la búsqueda, pues calcula y mueve los límites internamente.

<?php
/**
 *
 * Implementación del algoritmo de búsqueda binaria secuencial en un arreglo
 * usando PHP
 * Nota: este método sólo funciona con números
 *
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */

function busquedaBinaria(&$arreglo, $busqueda)
{
    $izquierda = 0;
    $derecha = count($arreglo) - 1;
    #Mientras el arreglo se pueda partir...
    while ($derecha >= $izquierda) {
        # Obtener el valor y elemento de la mitad del arreglo
        $indiceDelElementoMedio = floor(($izquierda + $derecha) / 2);
        $elementoDelMedio = $arreglo[$indiceDelElementoMedio];

        # ¿Lo que buscamos está en la mitad del arreglo? entonces regresa el índice
        if ($busqueda === $elementoDelMedio) {
            return $indiceDelElementoMedio;
        } else {
            # Si no, partimos el arreglo dependiendo de la búsqueda
            if ($busqueda > $elementoDelMedio) {
                # Si está a la derecha, lo partimos desde el medio + 1 hasta el elemento dado por derecha
                $izquierda = $indiceDelElementoMedio + 1;
            } else {
                # Si está a la izquierda, lo partimos desde el medio - 1 hasta el elemento dado por izquierda
                $derecha = $indiceDelElementoMedio - 1;
            }
        }
        # El ciclo continúa, pero ya cambiamos izquierda o derecha según haya sido el caso
    }
    # Si llegamos a este punto es porque la búsqueda no se encuentra
    return -1;

}

Así de fácil es. Igualmente es una búsqueda binaria pero usando un ciclo while.

Cómo usar la función

Podemos probarlo así:

<?php
$arreglo = [1, 5, 40, 45, 58, 77, 80, 200, 250];
$busqueda = 77;
$indice = busquedaBinaria($arreglo, $busqueda);
echo "El elemento $busqueda está en el índice $indice";

La salida es: El elemento 77 está en el índice 5

Sobre las cadenas

Aquí una pequeña nota: las cadenas se comparan de distinta manera, pues no podemos usar simples signos de comparación como con los números (aunque en JS sí). Para esto usamos la función strcmp.

El objetivo de este post es explicar la búsqueda binaria, pero recomiendo que sepas cómo funciona strcmp y he preparado un post para ello: uso de la función strcmp para comparar cadenas.

De ahí, el código es exactamente el mismo.

Búsqueda binaria en arreglo de cadenas usando recursividad

Lo mismo que hicimos para comparar números, pero ahora usando cadenas. Aquí el código igualmente en una función:

<?php
/**
 * 
 * Implementación del algoritmo de búsqueda binaria recursiva en un arreglo
 * usando PHP
 * Nota: este método sólo funciona con cadenas
 * 
 * Para saber cómo se comparan las cadenas, visita: 
 * https://parzibyte.me/blog/2018/10/22/comparar-cadenas-strcmp-php/
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */
 
function busquedaBinariaRecursiva(&$arreglo, $busqueda, $izquierda, $derecha)
{
 
    /*
    Comprobar si ya no podemos partir el arreglo
     */
    if ($izquierda > $derecha) {
        return -1;
    }
    # Obtener el valor y elemento de la mitad del arreglo
    $indiceDelElementoMedio = floor(($izquierda + $derecha) / 2);
    $elementoDelMedio = $arreglo[$indiceDelElementoMedio];
 
    # Esta función devuelve un número menor a 0 si la cadena 1 es menor que la cadena 2
    # en caso de que la 1 sea mayor que la 2, devuelve un número mayor a 0
    # y si ambas son iguales devuelve 0
    $resultadoDeLaComparacion = strcmp($busqueda, $elementoDelMedio);
 
    # ¿Lo que buscamos está en la mitad del arreglo? entonces regresa el índice
    if ($resultadoDeLaComparacion === 0) {
        return $indiceDelElementoMedio;
    } else {
        # Si no, partimos el arreglo dependiendo de la búsqueda
        if ($resultadoDeLaComparacion > 0) {
            # Si está a la derecha, lo partimos desde el medio + 1 hasta el elemento dado por derecha
            $izquierda = $indiceDelElementoMedio + 1;
            return busquedaBinariaRecursiva($arreglo, $busqueda, $izquierda, $derecha);
        } else {
            # Si está a la izquierda, lo partimos desde el medio - 1 hasta el elemento dado por izquierda
            $derecha = $indiceDelElementoMedio - 1;
            return busquedaBinariaRecursiva($arreglo, $busqueda, $izquierda, $derecha);
        }
    }
}

Buscar string en arreglo con búsqueda binaria

Podemos usar a la función así:

<?php
$arreglo = ["auto", "avispa", "avión", "computadora", "gato", "perro", "tarjeta"];
$busqueda = "computadora";
$izquierda = 0;
$derecha = count($arreglo) - 1;
$indice = busquedaBinariaRecursiva($arreglo, $busqueda, $izquierda, $derecha);
echo "El elemento $busqueda está en el índice $indice";

Con la salida que dice: El elemento computadora está en el índice 3

Búsqueda binaria en arreglo de cadenas con ciclo while

Usando strcmp y el ciclo while recorremos los límites, es decir, jugamos con ellos. Es lo mismo que hacemos con números pero sin usar operadores de comparación como < o >.

La función queda así:

<?php
/**
 *
 * Implementación del algoritmo de búsqueda binaria secuencial en un arreglo
 * usando PHP
 * Nota: este método sólo funciona con cadenas
 * Para saber cómo se comparan las cadenas, visita: 
 * https://parzibyte.me/blog/2018/10/22/comparar-cadenas-strcmp-php/
 *
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */
 
function busquedaBinaria(array &$arreglo, string $busqueda)
{
    $izquierda = 0;
    $derecha = count($arreglo) - 1;
    #Mientras el arreglo se pueda partir...
    while ($derecha >= $izquierda) {
        # Obtener el valor y elemento de la mitad del arreglo
        $indiceDelElementoMedio = floor(($izquierda + $derecha) / 2);
        $elementoDelMedio = $arreglo[$indiceDelElementoMedio];
 
        # Esta función devuelve un número menor a 0 si la cadena 1 es menor que la cadena 2
        # en caso de que la 1 sea mayor que la 2, devuelve un número mayor a 0
        # y si ambas son iguales devuelve 0
        $resultadoDeLaComparacion = strcmp($busqueda, $elementoDelMedio);
 
        # ¿Lo que buscamos está en la mitad del arreglo? entonces regresa el índice
        if ($resultadoDeLaComparacion === 0) {
            return $indiceDelElementoMedio;
        } else {
            # Si no, partimos el arreglo dependiendo de la búsqueda
            if ($resultadoDeLaComparacion > 0) {
                # Si está a la derecha, lo partimos desde el medio + 1 hasta el elemento dado por derecha
                $izquierda = $indiceDelElementoMedio + 1;
            } else {
                # Si está a la izquierda, lo partimos desde el medio - 1 hasta el elemento dado por izquierda
                $derecha = $indiceDelElementoMedio - 1;
            }
        }
        # El ciclo continúa, pero ya cambiamos izquierda o derecha según haya sido el caso
    }
    # Si llegamos a este punto es porque la búsqueda no se encuentra
    return -1;
 
}

Llamada a la función

Con este ejemplo de código podemos probarla:

<?php
$arreglo = ["auto", "avispa", "avión", "computadora", "gato", "perro", "tarjeta"];
$busqueda = "tarjeta";
$indice = busquedaBinaria($arreglo, $busqueda);
echo "El elemento $busqueda está en el índice $indice";

Si lo ejecutamos, esta es la salida:

El elemento tarjeta está en el índice 6