旋转数组的最小数字

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

 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0

思路：利用二分法，找到中间的数，然后和最左边的值进行比较，若大于最左边的数，则最左边从mid开始，若小于最右边值，则最右边从mid开始。若左中右三值相等，则取mid前后值中较小的数，并将其赋值给最右边，作为最右边的边界。

解法一：先使用二分法查找（O(logn)），如果左中右三个值相等，则进行顺序查找（O(n)）

 1 package Problem8;
 3 public class MinInReversingList {
9     /**
10      * @param args
11      * @throws Exception
12      */
13     public static int minElement(int array[]) throws Exception {
14         if (array == null || array.length <= 0) {   // 条件判断
16             throw new Exception("Invalid parameters");
17         }
18         int left = 0;
19         int right = array.length - 1;
20         int mid = left;
21         while (array[left] >= array[right]) {
22             // 跳出循环的条件
23             if (right - left == 1) {
24                 mid = right;
25                 break;
26             }
27             mid = (left + right) / 2;
28             if (array[left] == array[mid] && array[mid] == array[right]) {
29                 return minFromSortSearch(array,left,right);
30                 // 算法的核心思想
31             } else {
32                 if (array[mid] >= array[left]) {
33                     left = mid;
34                 }
35                 if (array[mid] <= array[right]) {
36                     right = mid;
37                 }
38             }
39         }
40         return array[mid];
41     }   //如果左中右三个数字相等时，顺序查找
43     public static int minFromSortSearch(int[] array,int start,int end) {    
44         int minEle = array[start];
45         for (int i = start+1; i <= end; i++) {
46             if (array[i] < minEle) {
47                 minEle = array[i];
48             }
49         }
50         return minEle;
51     }
53     // 测试
54     public static void main(String[] args) throws Exception {
55         // 功能测试：输入的数组是升序排序数组的一个旋转，数组中有重复数字或者没有重复数字
56         int array1[] = { 3, 4, 5, 1, 2 };
57         System.out.println(minElement(array1));
58         int array2[] = { 3, 4, 5, 3, 3 };
59         System.out.println(minElement(array2));
60         // 边界测试:输入的数组是一个升序排序数组、只包含一个数字的数组
61         int array3[] = { 3 };
62         System.out.println(minElement(array3));
63         // 特殊输入测试：输入null指针
64         int array4[] = null;
65         System.out.println(minElement(array4));
66     }
68 }

解法二：先使用二分法查找（O(logn)），若左中右三值相等，则取mid前后值中较小的数，并将其赋值给最右边，作为最右边的边界

public static int minNumberInRotateArray(int [] array) {
	    if (array == null || array.length == 0)
	        return 0;
	    int left = 0;
	    int right = array.length - 1;
	    int mid = 0;

	    while (array[left] >= array[right]) {
	        if(right - left <= 1) {
	            mid = right;
	            break;
	        }
	        mid = (left + right)/2;
	        if (array[left] == array[mid] && array[mid] == array[right]) {
	            if (array[left+1] != array[right-1]) {
	                mid = array[left+1] < array[right-1] ? left+1:right-1;
	                right = mid;
	            } else {
	              left++;
	              right--;
	            }
	        } else {
	          if (array[left] <= array[mid]) {
	              left = mid;
	          } else {
	              right = mid;
	          }
	        }
	    }
	    return array[mid];
	}

第二种解法不用顺序遍历整个数组，属于一种取巧的方法，可以应对特殊情况，如：{3,3,1,3,3,3}、{3,3,3,1,3,3}