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

#include<stdio.h>
  
/* Function to get index of ceiling of x in arr[low..high] */
int ceilSearch(int arr[], int low, int high, int x)
{
  int 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 program to check above functions */
int main()
{
   int arr[] = {1, 2, 8, 10, 10, 12, 19};
   int n = sizeof(arr)/sizeof(arr[0]);
   int x = 3;
   int index = ceilSearch(arr, 0, n-1, x);
   if(index == -1)
     printf("Ceiling of %d doesn't exist in array ", x);
   else
     printf("ceiling of %d is %d", x, arr[index]);
   getchar();
   return 0;
}

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

#include<stdio.h>
  
/* Function to get index of ceiling of x in arr[low..high]*/
int ceilSearch(int arr[], int low, int high, int x)
{
  int 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]*/
  mid = (low + high)/2;  /* low + (high - low)/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 program to check above functions */
int main()
{
   int arr[] = {1, 2, 8, 10, 10, 12, 19};
   int n = sizeof(arr)/sizeof(arr[0]);
   int x = 20;
   int index = ceilSearch(arr, 0, n-1, x);
   if(index == -1)
     printf("Ceiling of %d doesn't exist in array ", x);
   else  
     printf("ceiling of %d is %d", x, arr[index]);
   getchar();
   return 0;
}

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.