Log inSign up
easyGeeksforGeeksNot Started

Ceiling in a Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a sorted array arr of n integers and an integer x, find the ceiling of x in the array.

The ceiling of x is defined as the smallest element in `arr` that is greater than or equal to `x`. Return the 0-based index of the ceiling element. If no such element exists (i.e. all elements are smaller than x), return -1.

You must implement a solution in O(log n) runtime.

Example 1 · Exact Target Present:

Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 8
Output: 2
Explanation: 8 is present at index 2 (arr[2] = 8).

Example 2 · Target Between Elements:

Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 5
Output: 2
Explanation: Smallest element >= 5 is 8 at index 2.

Example 3 · Target Greater than All Elements:

Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 25
Output: -1
Explanation: No element is >= 25, so ceiling does not exist; return -1.

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i], x <= 106
  • arr is sorted in non-decreasing (ascending) order.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Ceiling invariant (arr[mid] >= x) and leftward contraction.
  • Understand why Ceiling corresponds directly to Lower Bound with -1 fallback.
  • Combine Floor and Ceiling into a single unified range query structure.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find smallest value >= target in sorted array
  • Find ceiling of a number
  • O(log N) search on monotonic sequence

Algorithmic Decision Tree:

  • Initialize low = 0, high = n - 1, ans = -1.
  • Calculate mid = low + (high - low) / 2.
  • If arr[mid] >= x: ans = mid, high = mid - 1 (search left for smaller candidate).
  • If arr[mid] < x: low = mid + 1 (search right).
  • Return ans.

Connected Patterns:

Floor in a Sorted ArrayLower BoundSearch Insert PositionUpper Bound

1. Linear Scan from Left

Intuition

Iterate from index 0 to n - 1. As soon as arr[i] >= x, return i immediately since it is the smallest element >= x. If loop completes, return -1.

When to apply: Unsorted collections or very small array sizes.

Algorithm

  1. Step 1: Iterate index i from 0 to arr.length - 1.
  2. Step 2: If arr[i] >= x, return index i immediately.
  3. Step 3: If loop completes without match, return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int findCeil(const vector<int>& arr, int x) {
7 for (int i = 0; i < (int)arr.size(); i++) {
8 if (arr[i] >= x) return i;
9 }
10 return -1;
11}
12
13int main() {
14 vector<int> arr = {1, 2, 8, 10, 11, 12, 19};
15 cout << "Linear Ceil of 5: " << findCeil(arr, 5) << endl;
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(N) — Worst case checks all N elements.
  • Space complexity: O(1) — Uses constant auxiliary memory.

2. Lower Bound Library Delegation

Intuition

Compute lb = lower_bound(arr, x). If lb < arr.length, return lb. Else return -1.

When to apply: When lower_bound is pre-implemented in standard libraries.

Algorithm

  1. Step 1: Compute lb = lower_bound(arr, x).
  2. Step 2: If lb < arr.length, return lb.
  3. Step 3: Else return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int findCeil(const vector<int>& arr, int x) {
8 auto it = lower_bound(arr.begin(), arr.end(), x);
9 if (it != arr.end()) {
10 return distance(arr.begin(), it);
11 }
12 return -1;
13}
14
15int main() {
16 vector<int> arr = {1, 2, 8, 10, 11, 12, 19};
17 cout << "Lower bound Ceil of 5: " << findCeil(arr, 5) << endl;
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(log N) — Lower bound executes in O(log N) iterations.
  • Space complexity: O(1) — Uses constant auxiliary memory.

3. Iterative Binary Search Ceiling (Gold Standard)

Intuition

Initialize ans = -1, low = 0, high = n - 1. While low <= high: compute mid. If arr[mid] >= x, record ans = mid and move left high = mid - 1 to find smaller values >= x. Else (arr[mid] < x), move right low = mid + 1. Return ans.

When to apply: Industry standard optimal solution for finding ceiling element in sorted collections.

Algorithm

  1. Step 1: Initialize low = 0, high = arr.length - 1, and ans = -1.
  2. Step 2: Enter while loop with condition low <= high.
  3. Step 3: Compute mid = low + (high - low) / 2 safely.
  4. Step 4: If arr[mid] >= x: update ans = mid and search left (high = mid - 1).
  5. Step 5: Else (arr[mid] < x): search right (low = mid + 1).
  6. Step 6: Return ans.

Ceiling in Sorted Array Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initialize low = 0, high = 6, ans = -1
Visual state
Values and pointers at this exact step
array
S
1
2
8
10
11
12
19
0
↑ low
1
2
3
↑ mid
4
5
6
↑ high
Variables at this step
low
0
high
6
mid
3
midVal
10
ans
3
Check / comparison
arr[mid] = 10 >= x = 5 -> TRUE
Decision / next transition
10 is >= 5 (valid ceiling candidate). Record ans = 3. Search left: high = mid - 1 = 2.
Why this step matters

Initialize low = 0, high = 6, ans = -1. Calculate mid = 0 + (6 - 0) / 2 = 3. arr[3] = 10.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int findCeil(const vector<int>& arr, int x) {
7 int low = 0, high = (int)arr.size() - 1;
8 int ans = -1;
9
10 while (low <= high) {
11 int mid = low + (high - low) / 2;
12
13 if (arr[mid] >= x) {
14 ans = mid; // arr[mid] >= x is a valid ceiling candidate
15 high = mid - 1; // Search left for smaller candidates >= x
16 } else {
17 low = mid + 1; // arr[mid] is too small, search right
18 }
19 }
20 return ans;
21}
22
23int main() {
24 vector<int> arr = {1, 2, 8, 10, 11, 12, 19};
25 int x = 5;
26 cout << "Ceiling index of " << x << " is: " << findCeil(arr, x) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval in O(log N) iterations.
  • Space complexity: O(1) — Uses constant O(1) auxiliary pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear ScanO(N)O(1)Scan array from left to right for first arr[i] >= x.Linear scan
2.Lower Bound Library DelegationO(log N)O(1)Use lower_bound directly.None
3.Iterative Binary SearchOptimalO(log N)O(1)Halve search space, recording mid and searching left whenever arr[mid] >= x.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Searching right on arr[mid] >= x instead of left.

Pitfall 2:

Returning index n instead of -1 when absent.

Crucial Edge Cases to Validate:

  • Target Larger than All Elements: arr = [2, 4, 6], x = 10 -> returns -1.
  • Target Smaller than All Elements: arr = [4, 6, 8], x = 1 -> returns index 0 (value 4).
  • Exact Match: arr = [2, 4, 6], x = 4 -> returns index 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain how Ceil and Floor are duals: Ceil searches left on >= x, Floor searches right on <= x.
  2. Show how both can be computed together in a single pass to answer 'find floor and ceiling' problems.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How is Ceiling related to Lower Bound?

2.If all elements in the array are strictly smaller than x, what is the ceiling index?

Back to DSA Sheet