问题
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
思路
这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是O(n)。但这个思路没有利用输入数组的特性。既然有时间复杂度更小的算法，我们容易想到二分查找，因为它的时间复杂度为O(logn)。这个问题是否可以运用二分查找呢？答案是肯定的。观察一下数组的特性，首先递增(称为递增a)，然后突然下降到最小值，然后再递增(称为递增b)。当然还有一种特殊情况，就是数组递增，中间没有下降，即旋转元素个数为0。
一般解法：找到中间下标，如果数组开始值小于中间下标对应的值，则表示中间下标属于第一个第一个递增，另开始下标等于中间下标，相反，如果中间下标对应的值小于结尾值，则表明，中间下标输入第二个递增，另结尾下标等于中间下标。直到开始下标和结尾下标相邻。
特殊情况：旋转个数为0，例如{1,2,3,4,5}，则可以通过第一个值小于最后一个值判断，直接输出第一个值。
packageoffer008;importjava.util.Scanner;/*** @Title: Main.java
* @Package: offer008
* @Description 旋转数组的最小数字
*@authorHan
* @date 2016-4-18 上午10:39:35
*@versionV1.0*/
public classMain {public static voidmain(String[] args) {
Scanner scanner= newScanner(System.in);int[] arr = null;int count = 0;while(scanner.hasNext()){//输入数组的大小
count =scanner.nextInt();
arr= new int[count];//输入数组
for(int i = 0; i < count; i++){
arr[i]=scanner.nextInt();
}
System.out.println(min(arr));
}
}/*** @Description 得到旋转数组中的最小值
*@authorHan
*@paramarr
*@returnmin*/
private static int min(int[] arr){//判断数组是否为空,长度是否为0
if(arr == null || arr.length == 0){throw new RuntimeException("Error Input");
}//头下标
int startIndex = 0;//尾下标
int endIndex = arr.length - 1;//中间下标
int middleIndex = 0;//如果数组中的第一个值小于了最后一个值，则表明该数组为一个递增数组，直接输出第一个元素即可
while(arr[startIndex] >=arr[endIndex]){//若该startIndex和endIndex相邻成立则表示endIndex指向的数字为最小值
if(endIndex - startIndex == 1){
startIndex=endIndex;break;
}
middleIndex= (startIndex + endIndex) / 2;//如果三个值相等，类似于1 0 1 1 1 1，则需要需要通过顺序查找出最小值
if(arr[middleIndex] == arr[startIndex] && arr[middleIndex] ==arr[endIndex]){returnminByOrder(arr, startIndex, endIndex);
}//若中间值大于startIndex指向的值，则移动startIndex到中间值
if(arr[middleIndex] >=arr[startIndex]){
startIndex=middleIndex;
}else if(arr[middleIndex] <=arr[endIndex]){
endIndex=middleIndex;
}
}returnarr[startIndex];
}/*** @Description 顺序查找出最小值
*@authorHan
*@paramarr
*@paramstartIndex
*@paramendIndex
*@return
*/
private static int minByOrder(int[] arr, int startIndex, intendIndex) {int min =arr[startIndex];for(int i = startIndex + 1; i <= endIndex; i++){if(arr[i]
min=arr[i];
}
}returnmin;
}
}
结果
