La búsqueda binaria es una técnica de búsqueda utilizada para buscar un elemento en una array ordenada. En este artículo, aprenderemos cómo implementar la búsqueda binaria en PHP de forma iterativa y recursiva. Dada una array de números, necesitamos buscar la presencia del elemento x en la array mediante la búsqueda binaria.
Ejemplos:
Input : 1 2 3 4 5
5
Output : 5 Exists
Input : 1 5 8
0
Output : 0 Doesnt Exist
Esta técnica de búsqueda es más eficiente que la búsqueda lineal.
Método 1 (iterativo) :
Pasos involucrados:
1) Ordenar la array como búsqueda binaria solo funciona en rangos ordenados
2) Calcular el elemento medio si el elemento que deseamos buscar es mayor que el elemento medio buscar en el lado derecho, de lo contrario buscar en el izquierdo.
3) Devuelve True si se encuentra el elemento.
<?php
function binarySearch(Array $arr, $x)
{
// check for empty array
if (count($arr) === 0) return false;
$low = 0;
$high = count($arr) - 1;
while ($low <= $high) {
// compute middle index
$mid = floor(($low + $high) / 2);
// element found at mid
if($arr[$mid] == $x) {
return true;
}
if ($x < $arr[$mid]) {
// search the left side of the array
$high = $mid -1;
}
else {
// search the right side of the array
$low = $mid + 1;
}
}
// If we reach here element x doesnt exist
return false;
}
// Driver code
$arr = array(1, 2, 3, 4, 5);
$value = 5;
if(binarySearch($arr, $value) == true) {
echo $value." Exists";
}
else {
echo $value." Doesnt Exist";
}
?>
Producción:
5 Exists
Método 2 (recursivo):
la recursividad es una forma en la que llamamos repetidamente a la misma función hasta que se iguala una condición base para finalizar la recursividad.
Continuando con los pasos del método 1 aquí, usamos la misma idea simplemente cambiando los parámetros de la función de manera recursiva y desglosando el problema.
function binarySearch(Array $arr, $start, $end, $x){
if ($end < $start)
return false;
$mid = floor(($end + $start)/2);
if ($arr[$mid] == $x)
return true;
elseif ($arr[$mid] > $x) {
// call binarySearch on [start, mid - 1]
return binarySearch($arr, $start, $mid - 1, $x);
}
else {
// call binarySearch on [mid + 1, end]
return binarySearch($arr, $mid + 1, $end, $x);
}
}
// Driver code
$arr = array(1, 2, 3, 4, 5);
$value = 5;
if(binarySearch($arr, 0, count($arr) - 1, $value) == true) {
echo $value." Exists";
}
else {
echo $value." Doesnt Exist";
}
Producción:
5 Exists
Funciones PHP relacionadas:
in_array() en PHP
array_key_exists() en PHP