题目11：旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾， 我们称之数组的旋转。输入一个递增排序的数组的一个旋转， 输出旋转数组的最小元素。
举例说明
数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
思路
一. 顺序遍历)
首先能想到的就是顺序遍历，数组中最小的元素即为整个旋转数组的最小元素，但算法时间复杂度为O(n)
二. 二分)
有序数组的查找大部分离不开二分。
由旋转数组的特性，因为经排序好的数组旋转得到的，所以由其特性可以知道，除了不旋转的情况（即原数组），旋转数组可以划分为两个排序的子数组，前面的子数组元素均大于后面的子数组元素，存在分界线，所以可以想到的就是利用二分查找法，实现时间复杂度为O(logn)
步骤
牢记：要求的是如果发生过旋转，第二个数组的第一个数。
1. 设置两个指针low,high
low指向数组的开始位置，也就是第一个数组的开始位置
high指向数组的终止位置，也就是第二个数组的结束位置
Mid在中点
2. 比较mid与low,high位置的数组值
一直逼近第二个数组的第一个数。
mid与low,high初始数组值关系
- 如果中间位置mid的数大于low指向的数，则mid在第一个数组中。故让low指向mid所指向的数，low指向的依然是数组1的数
- 如果中间位置mid的数小于high所指向的位置，则mid在第二个数组中。故让high指向mid指向的数，high指向的依然是数组2的数
- 知道low和high只差1（相邻），high指针的数组值就是所求
注意考虑以下几种情况的处理：
- 数组元素为空的情况（返回0）
- 数组元素只有一个的情况（返回该元素）
- 数组旋转0个元素，也就是没有旋转的情况，（最后返回mid对应的值，所以初始时令mid=low，遇到该情况while条件不成立，依然返回mid对应的值）
- 如果mid的数既等于p1位置数，又等于p2位置的数，这时候不能确定移哪个指针，就必须采用顺序查找的方法来寻找最小数
如，排序数组为{0,1,1,1,1}，旋转数组为{1,0,1,1,1}或者{1,1,1,0,1}，当为这两种情况时，mid=low=high，无法确定最小的元素在左还是在右，所以这个时候就需要采用顺序查找的方式。
代码实现
public class _11 {
public static int min(int[] arr) {
if (arr == null||arr.length< 1) {
throw new RuntimeException("Invalid input.");
}
if ( arr.length ==1) {
return arr[0];
}
int low = 0;// 开始处理的第一个位置
int high = arr.length - 1;// 开始处理的最后一个位置
int mid = low;// 设置初始值
// 确保low在前一个排好序的部分，high在排好序的后一个部分
while (arr[low] >= arr[high]) {//没中while就返回mid(low)
if (high - low == 1) {
return arr[high];
}
mid = low + (high - low) / 2;
// 如果三个数都相等，则需要进行顺序处理，从头到尾找最小的值
if (arr[mid] == arr[low] && arr[high] == arr[mid]) {
return minInorder(arr, low, high);
}
if (arr[mid] >= arr[low]) {// 如果arr[mid]在前一个排好序的部分
low = mid;
}
else if (arr[mid] <= arr[high]) {// 如果arr[mid]在后一个排好序的部分
high = mid;
}
}
return arr[mid];
}
private static int minInorder(int[] numbers, int start, int end) {//顺序处理
int result = numbers[start];//想象一个pivot拉低整条线
for (int i = start + 1; i <= end; i++) {
if (result > numbers[i]) {
result = numbers[i];
}
}
return result;
}
public static void main(String[] args) {
// 典型输入，单调升序的数组的一个旋转
int[] array1 = {3, 4, 5, 1, 2};//1
System.out.println(min(array1));
// 有重复数字，并且重复的数字刚好的最小的数字
int[] array2 = {3, 4, 5, 1, 1, 2};//1
System.out.println(min(array2));
// 有重复数字，但重复的数字不是第一个数字和最后一个数字
int[] array3 = {3, 4, 5, 1, 2, 2};//1
System.out.println(min(array3));
// 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
int[] array4 = {1, 0, 1, 1, 1};//0
System.out.println(min(array4));
// 单调升序数组，旋转0个元素，也就是单调升序数组本身
int[] array5 = {1, 2, 3, 4, 5};//1
System.out.println(min(array5));
// 数组中只有一个数字
int[] array6 = {2};//2
System.out.println(min(array6));
// 数组中数字都相同
int[] array7 = {1, 1, 1, 1, 1, 1, 1};//1
System.out.println(min(array7));
// 输入NULL
System.out.println(min(null));//java.lang.RuntimeException: Invalid input.
}
}
输出：
1
1
1
0
1
2
1
Exception in thread "main" java.lang.RuntimeException: Invalid input.
