# C Program to Find Ceiling of a Number in Sorted Array

• Write a program to find ceiling of a number in a sorted array.
• Algorithm to find the smallest number greater than or equal to X in a sorted integer array.

Given a sorted integer array and an integer X. We have to find the smallest number greater than or equal to X in input array.

Sorted array : [1 3 5 6 8 10 11 14 15 20].
• Ceiling : Ceiling of a number X is the smallest number greater than or equal to X in sorted array. If X is present in array then X is the ceiling otherwise smallest number greater than X.
• Ceiling of 9 is 10
• Ceiling of 14 is 14

Let inputArray be the given sorted array of size N.
Linear search : O(n)
Algorithm to find ceiling of a number using linear search
• If X is smaller than smallest element of inputArray(inputArray[0]). Then smallest element is ceiling element of X.
• If X is larger than largest element of inputArray(inputArray[N-1]), then no ceiling element exist for X.
• Traverse inputArray from index 0 to N-1 and find an index i where inputArray[i] < X && inputArray[i+1] >= X
• Return inputArray[i+1] as it is the first element greater than or equal to X.

## C program to find ceiling of a number in sorted array using linear search.

```#include <stdio.h>

/* This function prints the ceiling of K in sorted array */
void printCeilingElement(int *array, int size, int K){
int i;

/* If K is smaller that smallest element of array,
then smallest element is the ceiling of K*/
if(K <= array[0])
printf("%d ", array[0]);

/* If K is larger than the largest element of array,
then No ceiling element of K exist in array */
if(K > array[size-1])
printf("No Ceiling Element");

/* Traverse input array and search for appropriate
position of K in sorted array */
for(i = 0; i< size; i++){
if(K == array[i])
printf("%d", array[i]);

if(array[i] < K && array[i+1] > K)
printf("%d", array[i+1]);
}
}

int main(){
int array[10] = {1, 3, 5, 6, 8, 10, 11, 14, 15, 20};

printCeilingElement(array, 10, 12);

return 0;
}
```
Output
```14
```

By using customized binary search : O(LogN)
Algorithm to find smallest number greater than given number X.
• If X is smaller than smallest element of inputArray(inputArray[0]). Then smallest element is ceiling element of X.
• If X is larger than largest element of inputArray(inputArray[N-1]), then no ceiling element exist for X.
• Now do customized binary search.
• If X is larger than array[mid], then check if array[mid+1] is > X or recursively search in right sub array.
• If X is smaller than array[mid], then check if array[mid-1] is < X or recursively search in left sub array

## C program to find ceiling of a number in sorted array

```#include <stdio.h>

/* This function returns the index of ceiling of K in sorted array */
int getCeilingIndex(int *array, int left, int right, int K) {
int mid;

/* If K is smaller that smallest element of array,
then smallest element is the ceiling of K*/
if(K <= array[left])
return left;

/* If K is larger than the largest element of array,
then No ceiling element of K exist in array */
if(K > array[right])
return -1;

mid = (left + right)/2;
/* CUSTUMIZED BINARY SEARCH */
/* If K is equal to middle element, then return mid */
if(array[mid] == K)
return mid;

/* If K is larger than array[mid], then check if
array[mid+1] is > K or recursively search in right
sub array */
else if(array[mid] < K){
if(mid + 1 <= right && K <= array[mid+1])
return mid + 1;
else
return getCeilingIndex(array, mid+1, right, K);
}
/* If K is smaller than array[mid], then check if
array[mid-1] is < K or recursively search in right
sub array */
else {
if(mid - 1 >= left && K > array[mid-1])
return mid;
else
return getCeilingIndex(array, left, mid - 1, K);
}
}

int main(){
int array[10] = {1, 3, 5, 6, 8, 10, 11, 14, 15, 20};
int index = getCeilingIndex(array, 0, 9, 12);
if(index == -1){
printf("No Ceiling Element found in Array");
} else {
printf("Ceiling Element : %d", array[index]);
}
return 0;
}
```
Output
```14
```