Find Minimum in Rotated Sorted Array
Question Solution
Suppose a sorted array 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.
SOLUTION 1:
这个题目trick的地方在于，它的旋转pivot次数未知。所以有可能它转了一圈又转回了原处
所以我们代码要处理2种情况：
我们还是用二分法来做。比起全部扫一次，二分法可以做到LogN的复杂度。
1. Sorted
这种情况简单，先计算出mid的值，如果它处在左右的中间，证明这个数列是正常的sorted,直接返回左边。
我们的目的是要找出存在断口的地方。所以我们可以每次求一下mid的值，把mid
跟左边比一下，如果是正常序，就丢掉左边，反之丢掉右边，不断反复直到找到断口。
分析一下：
比如4 5 6 7 0 1 2 从中间断开后，它是由一个有序跟一个无序的序列组成的。
如果left = 0, right = 6,mid = 3, 那么4， 5， 6， 7 是正序， 7， 0， 1，
2是逆序，所以我们要丢掉左边。这样反复操作，直到数列中只有2个数字，就是断开处，这题我们会得到7，0，返回后一个就可以了。
以下图示简单描述了通过三步操作逐步逼近断口处。每一次我们可以扔掉一半，速度是LogN.
注意，丢掉半边时，mid不可以丢掉，因为有可能mid就是答案。
例子： 3， 1， 2 的时候，3， 1是逆序，1， 2是正序，如果你扔掉1，2你就丢掉了答案。
// Solution 1:
public int findMin1(int[] num) {
if (num == null || num.length == 0) {
return 0;
} if (num.length == 1) {
return num[0];
} // 至少有2个元素，才有讨论的价值
int l = 0;
int r = num.length - 1; while (l < r) {
int mid = l + (r - l)/2;
// Means that there is no rotate.
if (num[mid] >= num[l] && num[mid] <= num[r]) {
return num[0];
} // rotate > 0的情况
if (l == r - 1) {
// 当只余下2个元素的时候,这里是断点，右边的是小值
return num[r];
} if (num[mid] >= num[l]) {
// The left side is sorted. Discard left.
l = mid;
} else {
// The right side is sorted.
r = mid;
}
} return 0;
}
SOLUTION 2:
采用九章算法的二分法模板来解：
// bug 1: should not use l = m + 1 and r = m - 1.
// this may discard the minumul value.
A example: 3, 1, 2.
// solution 2:
public int findMin(int[] A) {
if (A == null || A.length == 0) {
return 0;
} if (A.length == 1) {
return A[0];
} else if (A.length == 2) {
return Math.min(A[0], A[1]);
} // 至少有3个元素，才有讨论的价值
int l = 0;
int r = A.length - 1; while (l < r - 1) {
int m = l + (r - l) / 2; // means that there is no rotate.
if (A[m] < A[r] && A[m] > A[l]) {
return A[0];
} // left side is sorted.
if (A[m] > A[l]) {
l = m;
} else {
r = m;
}
} return A[r];
}
while (l < r - 1) {
int m = l + (r - l) / 2;
// means that there is no rotate.
... 这里添加各种退出条件，比如找到了目标值等
// left side is sorted.
if (A[m] > A[l]) {
l = m;
} else {
r = m;
}
}
SOLUTION 3:
在解答2的基础之上，可以把判断是否rotated的statement去掉，然后每次丢弃有序数列时，先丢弃右边的。这样子即使是从未rotated的也没有关系，因为一直是丢右边的
直到余下左边最后2个。
public int findMin(int[] num) {
if (num == null || num.length == 0) {
return 0;
}
int l = 0;
int r = num.length - 1;
while (l < r - 1) {
int m = l + (r - l) / 2;
if (num[m] < num[r]) {
// bug 1: should not use l = m + 1 and r = m - 1.
// this may discard the minumul value.
r = m;
} else {
l = m;
}
}
return Math.min(num[l], num[r]);
}
SOLUTION 4:
在解答3的基础之上先，预判断是不是旋转过，这样如果没有旋转我们可以直接把解算出即可。
public int findMin(int[] num) {
if (num == null || num.length == ) {
return ;
}
int l = ;
int r = num.length - ;
if (num[l] < num[r]) {
return num[l];
}
while (l < r - ) {
int m = l + (r - l) / ;
if (num[m] < num[r]) {
// bug 1: should not use l = m + 1 and r = m - 1.
// this may discard the minumul value.
r = m;
} else {
l = m;
}
}
return Math.min(num[l], num[r]);
}
FOLLOW UP:
LeetCode 新题: Find Minimum in Rotated Sorted Array II 解题报告-二分法模板解法
GitHub：