Question
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
}
else if (nums[mid] <= nums[right]) {
right = mid;
}
}
return nums[left];
}
};
Problem Summary
Given a sorted array of a unique elements that has been rotated, find the minimum element in the array. The algorithm must have a time complexity of O(logn).
Core Idea
The key constraints is the O(logn) time complexity, which stongly suggests a Binary Search approach.
Although the entire array is not sorted, it is composed of two sorted subarrays. The minimum element is the “pivot” point where the rotation occurs (i.e., the first element of the second sorted array.)
The strategy is to use binary search to efficiently find this pivot point. We can determine which of the two sorted subarrays our mid pointer is in by comparing nums[mid] with the element at the right boundary, nums[right] .
Algorithm Logic
Initialize two pinters: left = 0 and right = num.size() - 1 .
Loop as long as left < right.
Calculate middle index using left + (right - left) / 2 . This formula is preferred over (left + right) / 2 to prevent potential integer overflow if the numbers are very large.
Compare num[mid] with nums[right] to decide which half of the array to discard:
If nums[mid] > nums[right] : This indicates that the mid element is in the larger, left sorted subarray. Therefore, the pivot must be in the right half. We discard the left half by setting left = mid + 1 .
If num[mid] ≤ nums[right] : This indicates that the segment from mid to right is sorted. The minimum element must be in the left half, and it’s possible that nums[mid] is the minimum itself. We discard the right half by setting right = mid .
The loop terminates when left and right converge to the same index. This index holds the minimum element in the array.
Return nums[left]
if nums[mid] > nums[right], then make the left flag be mid + 1.
else if nums[mid] ≤ nums[right], make the right flag be mid.
Example Walkthrough
Let's trace the algorithm with nums = [3, 4, 5, 1, 2].
