Given a sorted array of distinct integers and a target value, find the index of the ceiling of the target in the array.
The ceiling of a target is defined as the smallest element in the array that is greater than or equal to the target. If no such element exists (i.e., all elements are strictly smaller than the target), return -1.
Example 1
Input: arr = [1, 3, 5, 7, 9], target = 6
Output: 3
Explanation: The smallest value greater than or equal to 6 is 7, and it is present at index 3.
Example 2
Input: arr = [1, 3, 5, 7, 9], target = 10
Output: -1
Explanation: Every value in the array is smaller than 10, so no ceiling exists.
Brute Force Approach
The most direct idea is to move from left to right and stop at the first value that becomes greater than or equal to the target. Because the array is already sorted, the first such value is automatically the smallest valid one. So its index is the ceiling index. If the loop finishes and no such value is found, that means every element is smaller than the target, so the answer must be -1.
Algorithm
Start from index
0and check each element one by one.If the current value is greater than or equal to the target, return that index immediately because it is the first valid ceiling.
If the loop finishes without finding any valid value, return
-1.
Key Points
If the target is smaller than the first element, the answer is
0.If the target is greater than the last element, no ceiling exists, so return
-1.
Dry Run
Find Ceil Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the index of the smallest value greater than or equal to target. */ int findCeil(vector<int>& arr, int target) { // If the target is greater than the last element, no ceiling exists, so return -1. if (arr.empty() || target > arr.back()) { return -1; } // Check each index from left to right. for (int i = 0; i < (int)arr.size(); i++) { // The first value greater than or equal to target is the ceiling. if (arr[i] >= target) { return i; } } // if last element is less than target, // no ceil exits returns -1 return -1; }};// Driver code startsint main() { vector<int> arr = {1, 3, 5, 7, 9}; int target = 6; Solution obj; cout << obj.findCeil(arr, target) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the size of array, because in the worst case the whole array may need to be scanned.
Space Complexity: O(1), because only a few variables are used.
Optimal Approach
The useful observation is this: the ceiling index is just the first index where the value becomes greater than or equal to the target.
So whenever arr[mid] is greater than or equal to the target, that index can be an answer. But there may still be an earlier valid index on the left side, so the search should continue there.
If arr[mid] is smaller than the target, then mid and everything before it become useless, because none of those positions can hold the ceiling. This is the same lower-bound pattern. The only extra step is that if no valid index is found, the answer should be -1 instead of N.
Algorithm
Start with two pointers,
lowat0andhighat the last index.Keep a variable
answerasarr.size(). This helps track the first valid index if one is found.Find the middle index using
mid = low + (high - low) / 2, this helps avoiding interger overflow for higher values of high.If
arr[mid]is greater than or equal to the target, storemidinanswer, then move left to search for an even earlier valid index.If
arr[mid]is smaller than the target, move right because the ceiling cannot be on the left side.Continue until
lowbecomes greater thanhigh.If
answeris still equal to the array length, return-1. Otherwise, returnanswer.
Dry Run
Find Ceil optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the index of the smallest value greater than or equal to target. */ int findCeil(vector<int>& arr, int target) { // If the target is greater than the last element, no ceiling exists, so return -1. if (arr.empty() || target > arr.back()) { return -1; } // Left boundary of the current search range. int low = 0; // Right boundary of the current search range. int high = (int)arr.size() - 1; // Starts as arr.size() so it stays easy to detect when no ceiling exists. int answer = (int)arr.size(); // Keep searching while a valid range still exists. while (low <= high) { // Calculate the middle index safely. int mid = low + (high - low) / 2; // This index can be the ceiling, so store it and move left. if (arr[mid] >= target) { answer = mid; high = mid - 1; } else { // Values up to mid are too small, so move to the right half. low = mid + 1; } } // if last element is less than target, // no ceil exits(answer remains arr.size())returns -1 return answer == (int)arr.size() ? -1 : answer; }};// Driver code startsint main() { vector<int> arr = {1, 3, 5, 7, 9}; int target = 6; Solution obj; cout << obj.findCeil(arr, target) << endl; return 0;}Complexity Analysis
Time Complexity: O(log N), N is the size of array, because the search space becomes half in each step.
Space Complexity: O(1), because only a few variables are used.
Interview follow-up Questions
Because the ceiling must be the smallest valid value. In a sorted array, the first index that satisfies >= target automatically gives that smallest valid value.
Be the first to add a comment.