We can use Binary Search to find the minimum element in O(log n) time. The array is sorted but rotated. The key observation is that if we look at the middle element, it will be part of either the left sorted portion or the right sorted portion. We want to find the inflection point where the rotation happens. If nums[mid] > nums[right], it means the minimum must be to the right of mid. Otherwise, it is at mid or to the left of mid.
// Pseudocode: Linearly scan the array and keep track of the minimum.
// 1. Initialize min_val to the first element.
// 2. Iterate through each number in nums.
// 3. Update min_val = min(min_val, num).
// 4. Return min_val.
class Solution {
public:
int findMin(vector<int>& nums) {
int res = nums[0];
for (int n : nums) {
res = min(res, n);
}
return res;
}
};// Pseudocode:
// 1. Initialize left = 0, right = nums.size() - 1.
// 2. Loop while left < right.
// 3. Calculate mid = left + (right - left) / 2.
// 4. If nums[mid] > nums[right], the minimum is in the right half (left = mid + 1).
// 5. Else, the minimum is in the left half including mid (right = mid).
// 6. Return nums[left].
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > nums[r]) {
l = mid + 1;
} else {
r = mid;
}
}
return nums[l];
}
};Time: O(log n) because we are cutting the search space in half at each step using binary search. Space: O(1) because we only use two pointers.
- Array is not rotated (e.g., [1, 2, 3, 4, 5]). Handled correctly as nums[mid] will always be < nums[right].
- Array has 1 or 2 elements. Handled correctly.
- All elements are the same or duplicate elements exist? This problem states all elements are unique.
When dealing with rotated sorted arrays, always think of binary search. Compare mid with right to determine which half is sorted and where the inflection point lies. If nums[mid] > nums[right], the right side contains the drop.