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 rotated4
times.[0,1,2,4,5,6,7]
if it was rotated7
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 1:
Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Key Observations:
- A rotated sorted array is a sorted array that has been rotated at some pivot point. For example:
- Original array:
[1, 2, 3, 4, 5]
- Rotated arrays:
[4, 5, 1, 2, 3]
,[3, 4, 5, 1, 2]
- Original array:
- Minimum Element:
- The minimum element is the only element in the rotated array that is smaller than its predecessor.
- Alternatively, in the case of no rotation (e.g.,
[1, 2, 3, 4, 5]
), the first element is the smallest.
- Binary Search Approach:
- Since the array is sorted and rotated, we can use binary search to identify the minimum element in O(log n) time.
Steps to Solve:
- Binary Search:
- Set two pointers:
low = 0
(start of array) andhigh = n-1
(end of array). - While
low < high
, compute the middle index:mid = low + (high - low) / 2
. - Depending on the relationship between
arr[mid]
andarr[high]
:- If
arr[mid] > arr[high]
: The minimum must lie in the right half of the array (setlow = mid + 1
). - Otherwise, the minimum must be in the left half or at
mid
(sethigh = mid
).
- If
- When
low == high
, the minimum element is at indexlow
.
- Set two pointers:
- Return the Result:
- Output the element at
arr[low]
.
- Output the element at
Algorithm Complexity:
- Time Complexity:
Binary search operates in O(log n) time due to halving the search space in every iteration. - Space Complexity:
The algorithm uses O(1) space as we only manipulate indices and access the array directly.
Implementation in C++:
Here is the efficient implementation:
#include <iostream>
#include <vector>
using namespace std;
int findMinimum(const vector<int>& arr) {
int low = 0, high = arr.size() - 1;
// Binary search to find the minimum element
while (low < high) {
int mid = low + (high - low) / 2;
// If middle element is greater than the last element,
// the minimum must be in the right half
if (arr[mid] > arr[high]) {
low = mid + 1;
}
// Otherwise, the minimum is in the left half (or could be at mid)
else {
high = mid;
}
}
// At this point, low == high and points to the minimum element
return arr[low];
}
int main() {
vector<int> arr = {4, 5, 6, 7, 0, 1, 2}; // Example rotated array
cout << "The minimum element is: " << findMinimum(arr) << endl;
return 0;
}