如:{1,2,3,4,5}的一个旋转数组为{3,4,5,1,2} 该数组的最小值为1
初看题目我们最直观的解法并不难,遍历数组用俩个"指针"一前以后,当前面"指针"指向的元素比后面的"指针"指向的数组元素小时,这时我们就找到旋转数组中的最小元素,我们不难写出如下代码:
public static int findMin(int[] arr) {
// 如果数组是只有一个元素 则不是旋转数组同时也防止下边的i+1越界
if(arr == null || arr.length <= 1){
return -1;
}
for (int i =0 ; i < arr.length -1; i++) {
if (arr[i] > arr[i + 1]) {
return arr[i + 1];
}
}
return -1;
}
但是上面这种方法当数组的元素特别多时,效率是比较低的,不足以拿到offer,现在考虑用二分法对上面算法进行改良:
定义一个数组最左边的"指针"left和一个数组最右边的"指针"right,每次求俩个指针的中间值记为middle,如果left所对应的值要比middle小,那么说明数组还在递增中,最小值会在middle和right之间,这时候我们让left等于middle,继续用同样的方式缩小范围,如果middle要比right小,那么说明最小值在left和middle之间,让right等于middle,用同样的方式继续求下去,就能求到最小值啦。
public static int findMin(int []arr) {
int left = 0;
int right = arr.length;
while(left < right) {
int middle = (left + right) / 2;
if (arr[left] < arr[middle]) {
left = middle;
// 如果遇到相同的元素 我们就只能用遍历了
} else if(arr[left] == arr[middle]){
for(int i = left; i <= middle; i++) {
if(arr[i] < arr[middle]) {
return arr[i];
}
}
return arr[left];
} else{
right = middle;
}
if (right - left == 1) {
if(arr[right] > arr[left])
return arr[left];
else
return arr[right];
}
}
return arr[left];
}
当left对应的元素与right对应的元素相等时,这是特殊情况,这里选择遍历去找最小值。