Programa Php para techo en una array ordenada

Dada una array ordenada y un valor x, el techo de x es el elemento más pequeño de la array mayor o igual que x, y el piso es el elemento más grande menor o igual que x. Suponga que la array está ordenada en orden no decreciente. Escribe funciones eficientes para encontrar el suelo y el techo de x. 
Ejemplos: 
 

For example, let the input array be {1, 2, 8, 10, 10, 12, 19}
For x = 0:    floor doesn't exist in array,  ceil  = 1
For x = 1:    floor  = 1,  ceil  = 1
For x = 5:    floor  = 2,  ceil  = 8
For x = 20:   floor  = 19,  ceil doesn't exist in array

En los métodos a continuación, hemos implementado solo funciones de búsqueda de techo. La búsqueda de piso se puede implementar de la misma manera.
Método 1 (búsqueda lineal) 
Algoritmo para buscar el techo de x: 
1) Si x es menor o igual que el primer elemento en la array, devuelve 0 (índice del primer elemento) 
2) De lo contrario, busque linealmente un índice i tal que x se encuentre entre arr[i] y arr[i+1]. 
3) Si no encontramos un índice i en el paso 2, devuelve -1 
 

<?php
// Function to get index of 
// ceiling of x in arr[low..high] 
function ceilSearch($arr, $low, $high, $x)
{
  
    // If x is smaller than or equal 
    // to first element, then return 
    // the first element 
    if($x <= $arr[$low])
        return $low; 
      
    // Otherwise, linearly search
    // for ceil value 
    for($i = $low; $i < $high; $i++)
    {
        if($arr[$i] == $x)
            return $i;
      
        // if x lies between arr[i] and 
        // arr[i+1] including arr[i+1], 
        // then return arr[i+1] 
        if($arr[$i] < $x && 
           $arr[$i + 1] >= $x)
            return $i + 1;
    }     
      
    // If we reach here then x is greater 
    // than the last element of the array,
    // return -1 in this case 
    return -1;
}
  
// Driver Code
$arr = array(1, 2, 8, 10, 10, 12, 19);
$n = sizeof($arr);
$x = 3;
$index = ceilSearch($arr, 0, $n - 1, $x);
if($index == -1)
    echo("Ceiling of " . $x . 
         " doesn't exist in array ");
else
    echo("ceiling of " . $x . " is " . 
                        $arr[$index]);
  
// This code is contributed by Ajit.
?>

Producción : 

ceiling of 3 is 8

Complejidad de tiempo: O(n)
Método 2 (búsqueda binaria) 
En lugar de usar la búsqueda lineal, aquí se usa la búsqueda binaria para encontrar el índice. La búsqueda binaria reduce la complejidad del tiempo a O (Iniciar sesión). 
 

<?php
// PHP Program for Ceiling in 
// a sorted array
  
// Function to get index of ceiling
// of x in arr[low..high]
function ceilSearch($arr, $low, 
                    $high, $x)
{
    $mid; 
      
    /* If x is smaller than or 
       equal to the first element,
       then return the first element */
    if($x <= $arr[$low])
        return $low; 
      
    /* If x is greater than the
       last element, then return
       -1 */
    if($x > $arr[$high])
        return -1; 
      
    /* get the index of middle
       element of arr[low..high] */
    // low + (high - low)/2
    $mid = ($low + $high)/2; 
      
    /* If x is same as middle element,
       then return mid */
    if($arr[$mid] == $x)
        return $mid;
          
    /* If x is greater than arr[mid],
       then either arr[mid + 1]    is 
       ceiling of x or ceiling lies 
       in arr[mid+1...high] */
    else if($arr[$mid] < $x)
    {
        if($mid + 1 <= $high && 
           $x <= $arr[$mid + 1])
            return $mid + 1;
        else
            return ceilSearch($arr, $mid + 1, 
                              $high, $x);
    }
      
    /* If x is smaller than arr[mid],
       then either arr[mid] is ceiling
       of x or ceiling lies in 
       arr[low....mid-1] */
    else
    {
        if($mid - 1 >= $low && 
           $x > $arr[$mid - 1])
            return $mid;
        else
         return ceilSearch($arr, $low, 
                           $mid - 1, $x);
    }
}
  
// Driver Code
$arr = array(1, 2, 8, 10, 10, 12, 19);
$n = sizeof($arr);
$x = 20;
$index = ceilSearch($arr, 0, $n - 1, $x);
if($index == -1)
    echo("Ceiling of $x doesn't exist in array ");
else
    echo("ceiling of $x is"); 
    echo(isset($arr[$index]));
  
// This code is contributed by nitin mittal.
?>

Producción : 
 

Ceiling of 20 doesn't exist in array 

Complejidad de tiempo: O (Iniciar sesión)
 

Artículos relacionados:  
Piso en una array ordenada  
Encuentre piso y techo en una array no ordenada
Escriba comentarios si encuentra que alguno de los códigos/algoritmos anteriores es incorrecto, o encuentra mejores formas de resolver el mismo problema, o si desea compartir el código para la implementación del piso.
 

Consulte el artículo completo sobre Techo en una array ordenada para obtener más detalles.