close

Algoritmo de búsqueda binaria (Binary Search) en PHP: explicación, pasos y ejemplo

El algoritmo de búsqueda binaria es un método eficiente para encontrar un valor específico en una matriz ordenada. Este enfoque divide la matriz en partes más pequeñas y compara continuamente el valor en la posición media del rango de búsqueda con el valor objetivo. Si los valores coinciden, se encuentra el valor deseado; de lo contrario, el algoritmo continúa reduciendo el rango de búsqueda y repite el proceso hasta que se encuentra el valor o no quedan más elementos para examinar.

Pasos:

  1. Inicialice el rango de búsqueda: Comience seleccionando el rango de búsqueda desde la primera posición left  hasta la última posición right  de la matriz.
  2. Encuentre el punto medio: calcule el punto medio promediando las left posiciones y la derecha; este es el punto medio del rango de búsqueda.
  3. Comparar valores: compare el valor en el punto medio con el valor objetivo.
  4. Manejar el resultado de la comparación: si el valor en el punto medio coincide con el valor de destino, devolver esta posición. Si el valor en el punto medio es menor que el valor objetivo, actualice la posición izquierda a medio + 1 para buscar la mitad derecha. Si el valor en el punto medio es mayor que el valor objetivo, actualice la posición derecha al medio- 1 para buscar en la mitad izquierda.
  5. Repetir: Repita los pasos 2 a 4 hasta que se encuentre el valor o no haya más elementos para verificar left > right.

Ventajas y desventajas

ventajas:

  • Rendimiento eficiente: la complejidad de tiempo del algoritmo es O(log n), lo que lo hace altamente eficiente para manejar grandes conjuntos de datos.
  • Eficaz para grandes conjuntos de datos: la búsqueda binaria es eficaz para reducir la cantidad de elementos que se deben examinar rápidamente en busca de grandes conjuntos de datos.

Desventajas:

  • Aplicable solo a matrices ordenadas: el algoritmo solo funciona en matrices ordenadas.
  • Número variable de pasos: el número de pasos necesarios para encontrar el valor depende de su posición en la matriz, y puede tomar muchos pasos para valores cercanos a los extremos.

Ejemplo: búsqueda binaria para encontrar el valor 12 en una matriz ordenada en PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Explicación del ejemplo

  1. Comenzamos con el rango de búsqueda inicial desde la primera posición left = 0 hasta la última posición right = 6  de la matriz.
  2. Calculamos el punto medio(mid) promediando las posiciones izquierda y derecha; mid = 3. El valor medio es 12.
  3. Comparamos el valor en mid(12) con el valor objetivo(12) y encontramos una coincidencia, por lo que regresamos a la posición 3.
  4. El algoritmo finaliza y generamos el resultado "Valor 12 encontrado en la posición 3".