889109. Ceil in a Sorted Array
Easy
Ceil in a Sorted Array
Summary
The problem is to find the smallest integer that is greater than or equal to a given target value and is present in a sorted array. This problem involves binary search and searching concepts.
Detailed Explanation
The goal is to find the smallest integer that is greater than or equal to the target value and is present in the sorted array. We can achieve this by using binary search algorithm.
Here's a step-by-step breakdown of the solution:
- Start with two pointers,
lowandhigh, initialized to the start and end of the array respectively. - Calculate the mid index of the current range
[low, high]. - Compare the value at the mid index with the target value. If the value is greater than the target, update
hightomid - 1. Otherwise, updatelowtomid + 1. - Repeat steps 2-3 until
lowandhighconverge. - The smallest integer that is greater than or equal to the target value is at index
low.
Time complexity analysis: The time complexity of this algorithm is O(logn), where n is the size of the array.
Space complexity analysis: The space complexity of this algorithm is O(1) as we are only using a few extra variables for our pointers and mid index.
Optimized Solutions
Java
public int ceil(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] >= target) {
return arr[mid];
} else if (arr[mid] < target) {
low = mid + 1;
}
}
return -1; // or some default value
}