java旋转数组最大值,面试题8—求“旋转数组”的最小数字

旋转数组：把一个数组最开始的若干个数字搬到数组的末尾，我们称之为数组的旋转；例如：{3,4,5,1,2}为{1,2，3,4,5}的一个旋转

解题思路：旋转的数组可以看成是两个排好序的子数组，且前面的子数组大于或者等于后面的子数组，最小的元素是两个数组的分界线；(利用二分查找法一样)

(第一步)：用两个指针分别指向数组的第一个元素和最后一个元素

(第二步)：找到数组的中间元素，如果该数组位于前面的递增数组，那么它应该大于或者等于第一个指针指向的元素，此时该最小的元素应该位于该中间元素的后面

(第三步)：把第一个指针指向该中间元素，以这种方式缩小查找范围

(第四步)：找到数组的中间元素，如果该数组位于后面的递增数组，那么它应该小于或者等于第二个指针指向的元素，此时该最小的元素应该位于该中间元素的前面

(第五步)：把第二个指针指向该中间元素，以这种方式缩小查找范围

int Min(int *numbers,int length)

{

if(numbers=NULL||length<=0)

throw new std::exception("Invalid parameters");

int index1=0,index2=length-1;

int indexMid=index1;

while(numbers[index1]>=numbers[index2])

{

if(index2-index1==1)

{

indexMid=index2;

break;

}

indexMid=(index1+index2)/2;

if(numbers[index1]==numbers[indexMid]&&numbers[index1]==numbers[index2])

return MinInOrder(numbers,index1,index2);

if(numbers[indexMid]>=numbers[index1])

index1=indexMid;

if(numbers[indexMid]<=numbers[index1])

index2=indexMid;

}

return numbers[indexMid];

}

//依顺序查找

int MinInOrder(int *numbers,int index1,int index2)

{

int result=numbers[index1];

for(int i=index+1;i<=index2;i++)

{

if(result>numbers[i])

result=numbers[i];

}

return result;

}