题目描述

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

NOTE：若数组大小为 0，请返回 0。

解题思路

如果遇到从排序的数组中查找数字需要尝试二分查找法。

我们利用两个指针分别指向数组的第一个元素和最后一个元素，我们可以先找到数组中间的元素，如果该中间元素大于或等于第一个元素，则位于前面的非递减子数组，此时我们就可以把第一个指针指向该中间元素，这样就可以缩小寻找的范围，移动以后，第一个指针依然指向前面的非递减数组；

否则属于后面的非递减子数组，此时我们就可以把第二个指针指向该中间元素，移动以后，第二个指针依然指向后面的非递减数组。然后循环下去，最终第一个指针将指向前面子数组的最后一个元素，而第二个指针将会指向后面子数组的第一个元素，而第二个指针指向的刚好是最小的元素。循环结束。

PS：我们要注意在参考解题中main函数里的特例，如果两个指针以及中间的元素指向的三个数字相等，就只能顺序查找。

代码

public class Min {/*** 获取旋转数组的最小数字* @param numbers 旋转数组* @return 最小数字* @throws Exception*/public static int min(int[] numbers) throws Exception {if (numbers == null || numbers.length == 0) {throw new Exception("Invalid parameters");}int length = numbers.length;// index1永远为前一个非递减的数组指针int index1 = 0;// index2永远为后一个非递减的数组指针int index2 = length-1;// middle永远指向中间的值，当旋转数据就是原数组时，返回第1个数字int indexMid = index1;while (numbers[index1] >= numbers[index2]) {if (index2 - index1 == 1) {indexMid = index2;break;}indexMid = (index1 + index2) / 2;// 如果下标i, j, middle 指向的三个数字相等，就只能顺序查找if (numbers[index1] == numbers[index2] && numbers[index1] == numbers[indexMid]) {return minInOrder(numbers, index1, index2);}if (numbers[indexMid] >= numbers[index1]) {index1 = indexMid;} else if (numbers[indexMid] <= numbers[index2]) {index2 = indexMid;}}return numbers[indexMid];}/*** 顺序找出旋转数组中最小的值* 因为有序，只要找到第一个递减的值就可以返回了* @param numbers* @param index1* @param index2* @return*/public static int minInOrder(int[] numbers, int index1, int index2) {int result = numbers[index1];for (int i = index1+1; i <= index2; i++) {if (result > numbers[i]) {result = numbers[i];}}return result;}// 测试public static void main(String[] args) throws Exception {int[] numbers = {3,4,5,1,2};System.out.println(min(numbers));}
}

---

来自：
《剑指Offer》
Coding-Interviews/旋转数组的最小数字.md at master · todorex/Coding-Interviews