# Ceiling in a sorted array

Posted: 8 Jul, 2021

Difficulty: Moderate

#### Given a sorted array **A** of integers having size **N** and a number **X**. Your task is to return the ceiling of 'X'. for the given list. Return -1 if the ceiling does not exist.

#### Ceiling of X is the smallest element in the array greater than or equal to X.

**Note**: you are not allowed to use inbuild functions like lower_bound() etc.

##### Input Format :

```
The first line contains a single integer ‘T’ denoting the number of test cases to run. Then the test cases follow.
The first line of each test case contains two integers ‘N’ and 'X', where N represents the size of the array.
The next line contains N integers, denoting the elements of the given array.
```

##### Output Format :

```
For each test case print a single integer denoting the ceiling of X.
Output for each test case will be printed in a separate line,
```

##### Note :

```
You are not required to print anything; it has already been taken care of. Just implement the function.
```

##### Constraints :

```
1 <= T <= 10
1 <= N <= 2 * 10^5
1 <= ai <= 10^9
Time limit: 1 sec
```

##### Sample Input 1 :

```
2
6 5
1 2 3 4 5 6
6 2
1 1 3 4 4 5
```

##### Sample Output 1 :

```
5
3
```

##### Explanation of sample input 1 :

```
For test case 1:
5 is the element in the array greater than equal to X=5.
For test case 2:
3 is the element in the array greater than equal to X=2.
```

##### Sample Input 2 :

```
2
3 7
1 2 9
6 2
1 1 1 1 1 1
```

##### Sample Output 2 :

```
9
-1
```

Approach 1

Approach 2

This question is similar to finding lower_bound of X, Hence we can use binary search to solve it on our own.

Start from a search space of the entire array, each time reduce the search space to half, continue doing this until the search space size becomes 0.

The steps are as follows:

- Initialize Ans = -1
- Initialize L = 0 and H = N-1 (initial search space) and Mid = (L+H)/2
- If the middle element of search space is greater than equal to X, then store this value(a
_{Mid}) in ‘Ans’ and continue the search on the left half. ie: set H = MID - 1 - If the middle element of search space is lesser than X, then continue the search on the right half. ie: set L= Mid+1
- Continue the search till the L<=H condition is satisfied.
- Finally, return Ans.