Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
PseudoCode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
PseudoCode
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is the time complexity of binary search?
4.2.
Does binary search work only when it’s a sorted array?
4.3.
Is MergeSort a stable sorting algorithm?
5.
Conclusion
Last Updated: Mar 27, 2024

Ceiling in a sorted array

Author aniket verma
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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:

  1. Iterate over all elements of the sorted array.
  2. Maintain an initial variable to store the answer.
  3. Check each element if it’s smaller than the current answer and greater than x, and update it.
  4. 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

8end 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing.

Also if we notice an important fact in the problem, that the array gives to us is a sorted array. We didn’t make use of it. Now if we know that the given array is a sorted array, do we need to iterate over all elements? 

No, because we could reduce our search space i.e., if an array element say Ai >= x we know that all elements in the array greater than or equal to Ai will also be greater than or equal to x also. Hence we do need to check after Ai.   

So this gives us the intuition of using binary search algorithm to our advantage which also works on the same idea.

Following this approach will definitely improve the efficiency of the algorithm from O(n) to O(logn),  because we reduce our search space. 

 

Now we can formulate our approach:

  1. Use binary search to search for the answer if present in the array. 
  2. If the middle element is greater than x, then our answer will be either the current element or on the left of the current element.
  3. Else our answer will be present on the right.
  4. If we don’t find the answer, then return -1. 

 

Let’s look at the pseudoCode

PseudoCode

Algorithm

___________________________________________________________________

procedure findCeilingInASortedArray(arr, x, N):

___________________________________________________________________

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

2.    l, r ←0, N-1   # keep two pointers l, r for denoting our search space 

3.    while l <= r do

4.     mid ← l + (r - l) / 2 # compute the middle 

5.         If arr[mid] >= x do # check the condition 

6.              answer ← arr[mid]

7.               r ←mid - 1 # the answer lies on middle element’s left

8.        else do

9.              l ← mid + 1 # the answer lies on middle element’s right

10.        end if

11.   end while

12.  return answer # return the answer

13end 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;
    
    int l = 0, r = N-1; // maintain 2 pointers for keeping 
                        // track of the search space
    while(l<=r){
        int mid = l + (r-l)/2; // compute the middle element
        // if current condition is met
        if(arr[mid] >= x){
            answer = arr[mid]; // update the answer
            r = mid - 1; // the answer is either the current element or on its left
        }else{
            l = mid + 1; // the answer is on the right of the current element           
        }
    }
    
    // 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 maximum triplet sum in array is:  21

 

Complexity Analysis

Time Complexity: O(logn)

We are simply using a single binary search to compute our answer and hence the algorithm is taking O(logn) time.
Space complexity: O(1) at the worst case, as we are not using any auxiliary space. 

Hence we reached an efficient solution from a linear solution to a logarithmic solution. 

Frequently Asked Questions

What is the time complexity of binary search?

The time complexity of the binary search algorithm is O(logN). Where N is the number of elements we apply the search on.

Does binary search work only when it’s a sorted array?

No, it’s not always the case that binary search works only when it’s a sorted array. It’s important to understand the idea behind the binary search algorithm. 

Is MergeSort a stable sorting algorithm?

Yes, MergeSort is a stable sorting algorithm.

Conclusion

This article taught us how to solve the problem of finding the ceiling in a sorted array. We also saw how to approach the problem using a naive approach followed by an efficient solution. We discussed an iterative implementation using examples, pseudocode, and proper code in detail.

Recommended Problem - Merge K Sorted Arrays

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Plates Between Candles
Next article
Binary Search in Sorted Vector of Pairs
Live masterclass