## 1. 尋找旋轉排序數組中的最小值 I
假設一個旋轉排序的數組其起始位置是未知的（比如0 1 2 4 5 6 7 可能變成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
你可以假設數組中不存在重復的元素。
樣例
> 給出[4,5,6,7,0,1,2] 返回 0
**規則**
輸入：int a[] 一個有序數組旋轉后的數組
輸出：int 最小的值
case：
```
數組為null
數組大小為0
數組旋轉不變 [0,1,2,3,4,5,6]
數組旋轉 [6,0,1,2,3,4,5]
數組旋轉 [1,2,3,4,5,6,0]
數組旋轉 [2,3,4,5,6,0,1]
數組旋轉 [4,5,6,0,1,2,3]
```
**思路**
最簡單的思路當然是遍歷一下，復雜度為O(n)和O(1)
也可以使用一次堆排序，復雜度為O(logn)和O(1)
由于是部分有序的，可以考慮使用二分法，復雜度為O(logn)和O(1)
[0,1,2,3,4,5,6] 旋轉后的序列在[0,1,2,3,4,5,6,0,1,2,3,4,5,6] 從里面取相應的長度的數即可，從里面可以看到，最小值0的位置，旋轉初期在右側，最后在左側，可以選取mid與begin和end對比，例如
```
[1,2,3,4,5,6,0] begin=1 mid=4 end=0 當mid>end時說明最小值在右側
[5,6,0,1,2,3,4] begin=5 mid=1 end=4 當mid<begin時說明最小值在左側
```
這樣，我們可以使用二分法進行對比，需要注意的是:begin、mid和end的值如何設置，特別是邊界條件[0] [0,1]這種少于三個數據的情況，還有mid=min的情況。
我們可以設置只有兩個的時候就停止，因為最小數據必然在這兩個里面。而大于兩個時，如[2,0,1],mid<begin,在左側，這時應該從區間[0,2] -> [begin,mid] = [2,0] 在這里面尋找。這時因為，未旋轉的數組是有序的，單調遞增，而旋轉過后，只有不與原來的數組相同，那么一定是遞減的。因此如果出現單調遞減的，就說明最小值在這個范圍內。
**代碼**
```
public class Solution {
/*
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int a[]) {
if(a == null || a.length == 0) return -1; // 異常條件
int len = a.length;
if(a[0] < a[len-1]) { // 特殊情況，相當于沒有旋轉
return a[0];
}
return search(a,0,len-1); // 初始范圍
}
private int search(int a[],int begin,int end) {
if(begin == end) return a[begin]; // 如果只有一個數
if(begin+1 == end) return Math.min(a[begin], a[end]); // 如果只有兩個數
int mid = begin + (end - begin) / 2; // 計算mid
if(a[begin] > a[mid]) { // 左邊
return search(a,begin,mid);
}else if(a[mid] > a[end]) { // 右邊
return search(a,mid,end);
}
return -1;
}
}
```
上面的實現使用了遞歸，勢必造成需要一定的棧空間，可以改造成循環
```
public class Solution {
/*
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int a[]) {
if(a == null || a.length == 0) return -1;
int len = a.length;
if(a[0] < a[len-1]) {
return a[0];
}
int begin = 0 , end = a.length - 1;
while(true) { // 循環
if(begin == end) return a[begin];
if(begin+1 == end) return Math.min(a[begin], a[end]);
int mid = begin + (end - begin) / 2;
if(a[begin] > a[mid]) {
end = mid;
}else if(a[mid] > a[end]) {
begin = mid;
}
}
}
}
```
使用一次堆排序的程序
```
package com.shisj.study.offer.chapter1.revertnum;
/**
* 使用堆排序
* @author shisj
*
*/
public class SearchSmallest0 {
public int findMin(int a[]) {
if(a == null || a.length == 0) return -1;
int len = a.length;
int begin = (len-2)/2;
while(begin >=0) {
swap(a,begin,begin*2+1);
swap(a,begin,begin*2+2);
begin --;
}
return a[0];
}
private void swap(int a[],int parent,int child) {
if(child > a.length-1)return;
if(a[parent] > a[child]) {
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
}
}
}
```
## 2. 尋找旋轉排序數組中的最小值 II
假設一個旋轉排序的數組其起始位置是未知的（比如0 1 2 4 5 6 7 可能變成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
數組中可能存在重復的元素。
樣例：
給出[4,4,5,6,7,0,1,2] 返回 0
**規則**
輸入：int a[] 一個有序數組旋轉后的數組
輸出：int 最小的值
case：
```
數組為null
數組大小為0
數組旋轉不變 [0,0,0,0,1,1,2,3,4,6]
數組旋轉 [0,0,1,1,2,3,4,6,0,0]
數組旋轉 [1,1,2,3,4,6,0,0,0,0]
數組旋轉 [3,4,6,0,0,0,0,1,1,2]
```
**思路**
這次加入了重復元素，首先要判斷是否可以使用二分法，通過分析，在上一個題目的基礎上增加了相等的情形，如[1,1,1,-1,1] 這次，mid=1 begin=1 end=1 只能兩個都查找，然后比較大小了。
使用一次堆排序的話不收影響。
**規則**
```
public class Solution {
/*
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int a[]) {
if(a == null || a.length == 0) return -1;
int len = a.length;
if(a[0] < a[len-1]) {
return a[0];
}
return search(a,0,len-1);
}
private int search(int a[],int begin,int end) {
if(begin == end) return a[begin];
if(begin+1 == end) return Math.min(a[begin], a[end]);
int mid = begin + (end - begin) / 2;
if(a[begin] > a[mid]) {
return search(a,begin,mid);
}else if(a[mid] > a[end]) {
return search(a,mid,end);
}else{
int ax = search(a,begin,mid);
int bx = search(a,mid+1,end);
return Math.min(ax,bx);
}
}
}
```
