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 
 

// C# program to find celing
// in a sorted array
using System;
  
class GFG {
      
    // Function to get index of ceiling 
    // of x in arr[low..high] 
    static 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 code
    public static void Main()
    {
        int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
        int n = arr.Length;
        int x = 3;
        int index = ceilSearch(arr, 0, n - 1, x);
          
        if (index == -1)
            Console.Write("Ceiling of " + x +
                     " doesn't exist in array");
        else
            Console.Write("ceiling of " + x +
                         " is " + arr[index]);
    }
}
  
// This code is contributed by Sam007.

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

// C# program to find celing
// in a sorted array
using System;
  
class GFG {
      
    // Function to get index of ceiling
    // of x in arr[low..high]
    static 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 code
    public static void Main()
    {
        int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
        int n = arr.Length;
        int x = 8;
        int index = ceilSearch(arr, 0, n - 1, x);
        if (index == -1)
            Console.Write("Ceiling of " + x +
                      " doesn't exist in array");
        else
            Console.Write("ceiling of " + x + 
                            " is " + arr[index]);
    }
}
  
// This code is contributed by Sam007.

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.