1.题目简介
求一个旋转数组的最小值。（ 把一个数组从最开始的若干个元素搬到数组的末尾，即为旋转数组。）
- 输入：一个递增排序数组的旋转
- 输出：数组的最小值
- 例子：数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1.
2.思路分析
最直观的解法是从头到尾顺序遍历，这种方法的时间复杂度为O(n)。这里并没有用到旋转数组的知识，显然不合题意。
结合提议，旋转数组从有序数组中的得来的，经过旋转后得到的两个部分也为有序的。在有序数组中查找首选二分法，可以把时间复杂度变为O(n)。由于是把递增数组中最开始的若干个元素移到末尾，那么经过旋转后，数组开头的元素一定是大于等于末尾的元素，这是循环的条件。
和二分法一样设置三个指针，low、mid和high，分别指向数组中的开头、中间和结尾元素。如果开头元素小于等于中间元素，证明前半部分是递增的，要找的最小值在后半部分，此时把low指向mid；同样的，如果中间元素的指小于等于最后元素的值，说明后面是递增序列，要找的元素在前半部分，把high指向mid。
那什么时候找到呢？当Low和high相邻时，且high所指的元素就时最小值。
例子：
arr = {3,4,5,1,2} ,low=0,high=4;mid=2; 经过依次查找，arr[low]<arr[mid];证明前半部分时递增序列，要查找的值在后半部分。 所以令low=mid=2；mid=3,第二次查找，arr[mid]=1，arr[high]=2，arr[mid]<arr[high],要查找的在后半部分 所以令high = mid = 3; 由于low和high已经相邻，找到元素，跳出循环注意：还要考虑两种特殊情况
3.代码
/*用二分法，查找返回旋转数组的最小值，时间复杂度为O(n)*/ public static int getMinOfRoateArray(int[] arr,int len) throws Exception { int min=0; int low = 0; int high = len - 1; int mid = low; if(arr==null||len==0) { throw new Exception("the array is illegal"); } while(arr[low]>=arr[high]) { if(high-low==1) { //相邻时候找到 mid = high; break; } mid = (low+high)/2; //特殊情况，中间 左右的值相等，只能顺序查找了 if(arr[low]==arr[high] && arr[mid] == arr[low]) { min = arr[0]; for(int i = 1 ; i < len ; i++) { if(arr[i] 4.相关-二分查找
//array为要排序的整型数组/**非递归*/ public int binarysearch(int x) { if(array.isEmpty()) { return -1; } int low = 0; int high = array.size()-1; while(low <= high) { int mid =(int) (high+low)/2; if(x == array.get(mid)){ return mid+1; } else if(x array.get(mid)){ low = mid+1; } } return -1; } /**递归调用 * */ public int binarySearchR(int x , int low ,int high) { int mid = (low+high)/2; if(x < array.get(low)||x > array.get(high-1) ||low >high) { return -1; } if(x < array.get(mid)) { return binarySearchR(x,low, mid-1); } else if (x > array.get(mid)) { return binarySearchR(x,mid+1,high); } else { return mid+1; } }