在有序旋转数组中找到最小值
程序员文章站
2024-03-15 20:29:00
...
/**
* Created by lxw, [email protected] on 2017/11/5.
* 给定一个可能旋转过的有序数组arr,可能存在重复的值,返回arr中的最小值
*/
public class rotatedArrayMin {
public int getMin(int[] arr){
int low = 0;
int high = arr.length - 1;
int mid = 0;
while (low < high){
if(low == high - 1){
break;
}
if(arr[low] < arr[high]){
return arr[low];
}
mid = (low + high) / 2;
if(arr[low] > arr[mid]){
high = mid;
continue;
}
if(arr[mid] > arr[high]){
low =mid;
continue;
}
while (low < mid){
if(arr[low] == arr[mid]){
low++;
} else if(arr[low] < arr[mid]){
return arr[low];
} else {
high = mid;
break;
}
}
}
return Math.min(arr[low], arr[high]);
}
public static void main(String[] args){
rotatedArrayMin tmp = new rotatedArrayMin();
int[] arr = {6, 7, 1, 2, 3, 4, 5, 6};
System.out.println(tmp.getMin(arr));
}
}
上一篇: JUnit的简单使用