## 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);
}
}
}
```
