binaria_string_recursiva.php

<?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);
        }
    }
}