Programa Javascript 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 
 

<script>
  
/* Function to get index of ceiling of 
x in arr[low..high] */
function ceilSearch(arr, low, high, x) 
{ 
      
    let i; 
      
    /* 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 
  
    let arr = [1, 2, 8, 10, 10, 12, 19]; 
    let n = arr.length; 
    let x = 3; 
    let index = ceilSearch(arr, 0, n-1, x); 
    if(index == -1) 
        document.write("Ceiling of " + x + " doesn't exist in array "); 
    else
        document.write ("ceiling of " + x + " is " + arr[index]);  
  
  
</script>

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). 
 

<script>
// Javascript 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) 
{ 
    let 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 
let arr = [1, 2, 8, 10, 10, 12, 19]; 
let n = arr.length; 
let x = 20; 
let index = ceilSearch(arr, 0, n - 1, x); 
  
if(index == -1){
    document.write(`Ceiling of ${x} doesn't exist in array `); 
}else{
    document.write(`ceiling of ${x} is ${arr[index]}`);  
}
    
// This code is contributed by _saurabh_jaiswal. 
  
</script>

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.