剑指offer-----旋转数组的最小数字(java版)。
一、题目
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
二、例子
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
三、思路
对于数组{3,4,5,1,2},我们可以使用二分法的思想,使用2个指针,第一个指针指向头,第二个指针指向最后一个元素,可以将原数组看成2个子数组,二分法之后判断中间元素,如果中间元素大于index1的元素,则中间元素(mid)在第一个子数组,最小元素在mid后,如果中间元素小于index2的元素,则中间元素(mid)在第二个子数组,最小元素在mid之前。
对于特殊数组如{1,0,1,1,1,1},{1,1,1,1,0,1}使用二分法是无效的,因为index1和index2,mid的元素都是相同的,所以对于这种情况只能进行顺序遍历。
四 程序源码
public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length==0) return 0; int index1 = 0; int index2 = array.length-1; int mid = index1; while (array[index1]>=array[index2]){ if (index2 - index1 == 1){ mid = index2; break; } mid = (index1+index2)>>1; if (array[index1] == array[index2]&&array[mid] == array[index1]){ return find(array,index1,index2); } if (array[mid]>=array[index1]) index1 = mid; else if(array[mid]<=array[index2]) index2 = mid; } return array[mid]; } public int find(int[] array,int index1,int index2){ int result = array[index1]; for (int i=index1+1;i<=index2;i++){ if (result>array[i]) result = array[i]; } return result; } }