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