Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2] Output: 1
Example 2:
Input: [4,5,6,7,0,1,2] Output: 0
Related Topics:
Array, Binary Search
Similar Questions:
Use two pointers L and R to define the search range. Initially L = 0, R = N - 1.
If there is only one element, then we don't need to search. So the while condition should be L < R instead of L <= R.
Let M = (L + R) / 2. Since M might = L, we compare A[M] with A[R].
If A[M] > A[R], the min point must be to the right of A[M], so we let L = M + 1.
Otherwise, the min point must be to the left of A[M] including A[M], so we let R = M.
// OJ: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
int findMin(vector<int>& A) {
int L = 0, R = A.size() - 1;
while (L < R) {
int M = (L + R) / 2;
if (A[M] > A[R]) L = M + 1;
else R = M;
}
return A[L];
}
};