一个数组先升序再降序，用最优时间复杂度，求最大值？例如[1,2,2,2,2,3,1]

Question

一个数组先升序再降序，求最大值？例如[1,2,2,2,2,3,1]，用最优时间复杂度，算法实现获取最大值3

Answer 1

===更新去掉了递归、数组复制，函数返回值改为索引以方便处理空数组的情况
publicclassMaxFinder{
publicstaticvoidmain(String[]args){
int[]arr={2,3,3,3,7,13,22};
System.out.println(arr[getMaxPos(arr)]);
}
publicstaticintgetMaxPos(int[]arr){
intlen=arr.length;
if(len>=2){
intmin=0,
max=len-1;//最大值位置的索引范围闭区间
intmid,left;
while(max-min>1){
mid=min+(max-min)/2;
left=mid-1;
while(left>=min){
if(arr[left]>arr[mid]){
max=left;
break;
}elseif(arr[left]min=mid;
break;
}else{
if(left==min){
min=mid;
}
left--;
}
}
}
returnarr[max]>arr[min]?max:min;
}elseif(len==1){
return0;
}else{
return-1;
}
}
}
===原答案
publicclassTest{
publicstaticvoidmain(String[]args){
int[]arr={1,2,2,2,2,3,1};
System.out.println(getMax(arr));
}
publicstaticintgetMax(int[]arr){
intlen=arr.length;
if(len>2){
intmid=len/2,
left=mid-1;
while(left>=0){
if(arr[left]>arr[mid]){
returngetMax(Arrays.copyOfRange(arr,0,left+1));
}elseif(arr[left]returngetMax(Arrays.copyOfRange(arr,mid,arr.length));
}else{
left--;
}
}
//comehereonlyifarr[0]toarr[mid]areallthesame
returngetMax(Arrays.copyOfRange(arr,mid,arr.length));
}elseif(len==2){
returnarr[0]>arr[1]?arr[0]:arr[1];
}else{
returnarr[0];
}
}
}
                            

Answer 2

/**
*使用二分查找法
*@paramarr:先升序在降序的数组
*@paramlow:数组最小的索引
*@paramhigh:数组最大的索引
*@return:返回数组中的最大值
*/
publicstaticintgetMax(int[]arr,intlow,inthigh){
while(low{
intmid=low+((high-low)>>1);
if(arr[mid]>arr[mid+1]){
high=mid;
}
elseif(arr[mid]low=mid+1;
}
else//arr[mid]和arr[mid+1]相等的情况
{
if(mid-1>=low)//防止数组范围越界[low~high]
{
if(arr[mid-1]>arr[mid])
{
high=mid-1;
}
elseif(arr[mid-1]{
low=mid+1;
}
else//如果arr[mid-1]和arr[mid]相等，即arr[mid-1]，arr[mid],arr[mid+1]都相等，
//那么就不能确定最大值在mid左边还是在mid右边，所以分别对mid左边和mid右边递归求最大
//值，然后比较
{
intone=getMax(arr,low,mid-1);
inttwo=getMax(arr,mid+1,high);
returnone>two?one:two;
}
}
else{//如果mid-1returnarr[low];
}
}
}
returnarr[low];
}