一、题目

把一个数组最开始的若干个元素搬到数组的末尾， 我们称之数组的旋转。输入一个递增排序的数组的一个旋转， 输出旋转数组的最小元素。例如数组{3,4,5,1,2 ｝为｛ 1,2,3,4,5}的一个旋转，该数组的最小值为1。

二、解题思路

Step1.和二分查找法一样，我们用两个指针分别指向数组的第一个元素和最后一个元素。

Step2.接着我们可以找到数组中间的元素：

如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素，这样可以缩小寻找的范围。如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。

Step3.接下来我们再用更新之后的两个指针，重复做新一轮的查找。

三、解题代码

  1. public class Test {  
  3.     /** 
  4.      * @param numbers 旋转数组 
  5.      * @return 数组的最小值 
  6.      */  
  7.     public static int min(int[] numbers) {  
  8.         // 判断输入是否合法  
  9.         if (numbers == null || numbers.length == 0) {  
  10.             throw new RuntimeException("Invalid input.");  
  11.         }  
  13.         // 开始处理的第一个位置  
  14.         int lo = 0;  
  15.         // 开始处理的最后一个位置  
  16.         int hi = numbers.length - 1;  
  17.         // 设置初始值  
  18.         int mi = lo;  
  20.         // 确保lo在前一个排好序的部分，hi在排好序的后一个部分  
  21.         while (numbers[lo] >= numbers[hi]) {  
  22.             // 当处理范围只有两个数据时，返回后一个结果  
  23.             // 因为numbers[lo] >= numbers[hi]总是成立，后一个结果对应的是最小的值  
  24.             if (hi - lo == 1) {  
  25.                 return numbers[hi];  
  26.             }  
  28.             // 取中间的位置  
  29.             mi = lo + (hi - lo) / 2;  
  31.             // 如果三个数都相等，则需要进行顺序处理，从头到尾找最小的值  
  32.             if (numbers[mi] == numbers[lo] && numbers[hi] == numbers[mi]) {  
  33.                 return minInorder(numbers, lo, hi);  
  34.             }  
  36.             // 如果中间位置对应的值在前一个排好序的部分，将lo设置为新的处理位置  
  37.             if (numbers[mi] >= numbers[lo]) {  
  38.                 lo = mi;  
  39.             }  
  40.             // 如果中间位置对应的值在后一个排好序的部分，将hi设置为新的处理位置  
  41.             else if (numbers[mi] <= numbers[hi]) {  
  42.                 hi = mi;  
  43.             }  
  44.         }  
  46.         // 返回最终的处理结果  
  47.         return numbers[mi];  
  48.     }  
  50.     /** 
  51.      * 找数组中的最小值 
  52.      * 
  53.      * @param numbers 数组 
  54.      * @param start   数组的起始位置 
  55.      * @param end     数组的结束位置 
  56.      * @return 找到的最小的数 
  57.      */  
  58.     public static int minInorder(int[] numbers, int start, int end) {  
  59.         int result = numbers[start];  
  60.         for (int i = start + 1; i <= end; i++) {  
  61.             if (result > numbers[i]) {  
  62.                 result = numbers[i];  
  63.             }  
  64.         }  
  65.         return result;  
  66.     }    
  67. }