今天看到LeetCode OJ题目下方多了“Show Tags”功能。我觉着挺好，方便刚開始学习的人分类练习。同一时候也是解题时的思路提示。
【题目】
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.
【解法】
题目比較简单，直接看代码吧，可是要想把代码写得美丽并不easy啊。
O(n)非常好写，O(lgn)要好好捋捋思路。
public class Solution {
// O(n) simple
public int findMin1(int[] num) {
int len = num.length;
if (len == 1) {
return num[0];
}
for (int i = 1; i < len; i++) {
if (num[i] < num[i-1]) {
return num[i];
}
}
return num[0];
// 尼玛，看成找中间数了
// if (len % 2 != 0) { //len is odd
// return num[(begin+len/2)%len];
// } else { //len is even
// return (num[(begin+len/2-1)%len] + num[(begin+len/2)%len]) / 2;
// }
}
// O(lgn) not that good
public int findMin2(int[] num) {
int len = num.length;
if (len == 1) return num[0];
int left = 0, right = len-1;
while (left < right) {
if ((right-left) == 1) return Math.min(num[left], num[right]);
if (num[left] <= num[right]) return num[left];
int mid = (left + right) / 2;
if (num[mid] < num[right]) {
right = mid;
} else if (num[left] < num[mid]) {
left = mid;
}
}
return num[left];
}
// O(lgn) optimized iteratively
public int findMin3(int[] num) {
int len = num.length;
if (len == 1) return num[0];
int left = 0, right = len-1;
while (num[left] > num[right]) { // good idea
int mid = (left + right) / 2;
if (num[mid] > num[right]) {
left = mid + 1;
} else {
right = mid; // be careful, not mid-1, as num[mid] maybe the minimum
}
}
return num[left];
}
// O(lgn) optimized recursively
public int findMin(int[] num) {
return find(num, 0, num.length-1);
}
public int find(int[] num, int left, int right) {
if (num[left] <= num[right]) {
return num[left];
}
int mid = (left + right) / 2;
if (num[mid] > num[right]) {
return find(num, mid+1, right);
}
return find(num, left, mid);
}
}