## Introduction

In this blog, we will discuss how to find the ceiling in a sorted array. Such problems are fairly common interview questions as well asked in many contests. Before solving the problem, it’s recommended to have a good understanding of __linear search__ and __binary search__. In this Blog we will dive deep into each detail to get a firm hold over how we can reach from a brute force solution to an optimal solution.

Also see, __Array Implementation of Queue__ and __Rabin Karp Algorithm__

### Problem Statement

Given two integers, n and x and a sorted array of integers of length n. The task is to find the smallest element in the array which is greater than or equal to the integer x. In case the ceil doesn’t exist in the array return -1.

### Sample Example

```
Input:
N, x and array of length N,
N = 7, x = 5
Arr = {2, 3, 9, 11, 11, 13, 20}
Output: 9
Explanation: The smallest element in the array that is just greater than x = 5 is 9. Hence the answer is 9.
```

## Brute Force Approach

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach is to iterate through the array, do a linear search and find the smallest element that is just greater than the value of ‘x’ and that will be our ceiling in a sorted array.

So the naive/basic approach could be formulated as:

- Iterate over all elements of the sorted array.
- Maintain an initial variable to store the answer.
- Check each element if it’s smaller than the current answer and greater than x, and update it.
- Return the answer.

Now let’s look at the PseudoCode.

### PseudoCode

**Algorithm**

___________________________________________________________________

**procedure** findCeilingInASortedArray(arr, x, N):

___________________________________________________________________

**1.** answer ← ∞ **#initially the answer is set to infinity.**

**2. for** each element **in **arr **do** **# for every element in the array **

**3.** ** if **current_element >= x **and ** current_element < answer **do**

**4. **answer ← current_element** #check if condition meets, update the result **

**5. end if**

**6. end for**

**7. return **answer **# return the answer**

**8**. **end procedure**

___________________________________________________________________

### Implementation in C++

```
// program to compute the ceiling in a sorted array
#include <bits/stdc++.h>
using namespace std;
// function to compute the ceiling in a sorted array
int CeilingInASortedArray(int arr[], int N, int x) {
int answer = INT_MAX;
// iterate over all elements and check if the
// condition satisfies or not
for(int i=0; i<N; ++i){
// check the condition
if(arr[i] >= x and arr[i] < answer){
answer = arr[i]; // update the result
}
}
// if the answer is not found
if(answer==INT_MAX)
answer = -1; // update the answer to -1
return answer; // return the answer
}
int main() {
// initialise the input parameters here
int N = 7; // store the size of the array
int x = 5; // store the value of x.
int arr[] = {2, 3, 9, 11, 11, 13, 20}; // store the array
// compute the ceiling in a sorted array
int answer = CeilingInASortedArray(arr, N, x);
// print the answer
cout<<"The ceiling in a sorted array is: "<<answer;
return 0;
}
```

**Output:**

`The ceiling in a sorted array is: 9`

####

Complexity Analysis

**Time Complexity:** O(n)

This is because we iterate through the entire array once. Basically, we are doing a linear search which will take O(n) time.

**Space complexity**: O(1) at the worst case because no extra space is used.

The above algorithm works in O(n) time. Can we improve our solution?? So let’s think about an efficient approach to solve the problem.