⬅ Previous Topic
Search in Rotated Sorted Array with DuplicatesNext Topic ⮕
Find Rotation Count in Sorted Array⬅ Previous Topic
Search in Rotated Sorted Array with DuplicatesNext Topic ⮕
Find Rotation Count in Sorted ArrayTopic Contents
Given a rotated sorted array of unique integers, your task is to find the minimum element in the array.
A rotated sorted array is an array that was originally sorted in increasing order, but then some leading elements were moved to the end. For example, [1, 2, 3, 4, 5]
could become [3, 4, 5, 1, 2]
.
The array contains no duplicate elements. If the array is empty, return -1
.
start = 0
and end = n - 1
.start < end
:mid = start + (end - start) / 2
.arr[mid] > arr[end]
, it means the minimum is in the right half, so set start = mid + 1
.mid
, so set end = mid
.arr[start]
is the minimum element.public class RotatedArrayMinimum {
public static int findMin(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (nums[mid] > nums[end]) {
// Minimum must be in the right half
start = mid + 1;
} else {
// Minimum could be at mid or to the left
end = mid;
}
}
return nums[start]; // or nums[end], both are same here
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
System.out.println("Minimum Element: " + findMin(nums));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | When the array is not rotated and the first element is the minimum. |
Average Case | O(log n) | Each iteration of binary search reduces the array size by half, giving logarithmic performance. |
Worst Case | O(log n) | In the worst case, the binary search continues until only one element remains. |
O(1)
Explanation: Only a few pointers are used, and no extra space is required.
⬅ Previous Topic
Search in Rotated Sorted Array with DuplicatesNext Topic ⮕
Find Rotation Count in Sorted ArrayYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.