Find Ceiling Element in Sorted Array
At Lenskart, efficiently managing our vast product catalog is crucial. Imagine our product SKUs are sorted by a specific metric, like a unique identifier or a composite score. When a customer searches for a product or our internal systems need to locate the first product meeting a certain threshold (e.g., a SKU ID greater than or equal to a specific value), we need a rapid way to find that item. This problem challenges you to implement an efficient search algorithm for such a scenario.
Implement a function findCeiling that takes a sorted array of integers arr and an integer target. Your task is to return the 0-based index of the first element in arr that is greater than or equal to target. If no such element exists in the array, the function should return -1.
arr: An array of integers, sorted in non-decreasing order.target: An integer value.arr that is greater than or equal to target. If no such element exists, return -1.arr is empty, return -1, as no elements exist.target is greater than all elements in arr, return -1, as no element satisfies the condition.target is smaller than or equal to the first element in arr, you should return the index of the first element (index 0).arr can contain duplicate values. If multiple elements are equal to target, you should still return the index of the first occurrence that satisfies the 'greater than or equal' condition.Examples
Example 1
Input:
arr = [1, 3, 5, 7, 9], target = 6
Output:
3
Note:
The first element greater than or equal to 6 is 7, which is at index 3.
Example 2
Input:
arr = [10, 20, 30, 40], target = 5
Output:
0
Note:
The first element greater than or equal to 5 is 10, which is at index 0.
Example 3
Input:
arr = [10, 20, 30, 40], target = 45
Output:
-1
Note:
There is no element in the array greater than or equal to 45.
Example 4
Input:
arr = [2, 4, 4, 6, 8], target = 4
Output:
1
Note:
The first element greater than or equal to 4 is 4, which is at index 1. Even though arr[2] is also 4, we need the first occurrence.
Constraints
0 <= arr.length <= 10^5-10^9 <= arr[i], target <= 10^9arr is sorted in non-decreasing order.arr is indeed sorted. Assume it always is.Loading editor...