find minimum in rotated sorted array II
旋转数组找到最小值,其中数组有重复值
使用二分法,最右的值小于中间值,那么最小值在右边。left就应该mid+1的地方,否则最小的值在左边,right=mid
当有重复值,即相等的时候,直接left加1呗,或者right--
public static int findmin1(int[] arr){
int left =0;
int right = arr.length-1;
while(left<right){
int mid = (left+right)/2;
System.out.println(mid);
if(arr[right]<arr[mid]){
left=mid+1;
} else if(arr[right]>arr[mid]) {
right=mid;
} else{
right--;
}
}
System.out.println(arr[left]);
return arr[left];
}
public static void main(String[] args){
int[] arr={3,3,4,4,-1,1};
findmin1(arr);
}
网友评论