题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{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}