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.
518+ registered 
