Try This Problem First
Platform: GeeksforGeeks
👉 Try this problem here: Ceil in a Sorted Array – GeeksforGeeks
Problem Statement
You are given a sorted array arr[] and an integer x. Your task is to find the index of the smallest element in the array that is greater than or equal to x.
- If no such element exists, return
-1. - If multiple elements equal the ceil, return the first occurrence.
Example:
Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 5
Output: 2
Explanation: Smallest element ≥ 5 is 8 at index 2.
Intuition
Think of the problem as finding the first step you can reach without falling short:
- The ceil of x is the smallest number ≥ x.
- Since the array is sorted, we can use binary search to quickly locate the answer instead of checking each element.
Linear search is simple but slow for large arrays. Binary search gives an efficient O(log n) solution.
Multiple Approaches
1️⃣ Linear Search (Easy to Understand)
int ans = -1;
for(int i = 0; i < arr.length; i++){
if(arr[i] >= x){
ans = i; // first occurrence
break;
}
}
return ans;
- Time Complexity: O(n)
- Space Complexity: O(1)
- ✅ Works for small arrays
- ❌ Slow for large arrays
2️⃣ Binary Search (Optimized & Fast)
int ans = -1;
int low = 0, high = arr.length - 1;
while(low <= high){
int mid = low + (high - low)/2;
if(arr[mid] == x){
ans = mid;
high = mid - 1; // move left for first occurrence
} else if(arr[mid] > x){
ans = mid; // candidate ceil
high = mid - 1; // move left
} else {
low = mid + 1; // arr[mid] < x → move right
}
}
return ans;
- Time Complexity: O(log n)
- Space Complexity: O(1)
- ✅ Efficient for large arrays
- ✅ Automatically returns first occurrence
Dry Run
Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 5
| Step | low | high | mid | arr[mid] | ans | Action |
| 1 | 0 | 6 | 3 | 10 | 3 | arr[mid] > x → move left |
| 2 | 0 | 2 | 1 | 2 | 3 | arr[mid] < x → move right |
| 3 | 2 | 2 | 2 | 8 | 2 | arr[mid] > x → move left |
| 4 | 2 | 1 | - | - | 2 | low > high → stop, return 2 |
✅ Binary search finds ceil = 8 at index 2.
Why This Problem is Important
- Teaches binary search for first occurrence
- Strengthens understanding of ceil/floor concepts
- Visualization through story improves understanding and retention
- Prepares for coding interviews and competitive programming
Conclusion
- Linear search: simple but slow (
O(n)) - Binary search: fast and efficient (
O(log n)) - Story-based visualization helps learn, not just memorize
- Using numbers on books in images makes abstract concepts concrete
