借用二分查找的思路,同时关注最小数在数组中的特点
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 1){
return array[0];
}
int i = 0;
int j = array.length-1;
int min = i;
// 前指针的值大于后指针的值,即最小值存在两个指针中间
// 否则,即前指针为最小值。
int temp;
while(array[i] >= array[j]){
// 前后指针相邻,即找到最小值,最小值为后一个指针
if(j - i == 1){
min = j;
break;
}
temp = (j + i) / 2;
// 前中后三个位置的值相等,只能按顺序查找
if(array[i] == array[temp] && array[j] == array[temp]){
return find(array,i,j);
}
if(array[i] < array[temp]){
// 前指针的值 < 中指针的值,移动前指针到中指针的位置
i = temp;
} else if (array[i] > array[temp]){
// 前指针的值 > 中指针的值,移动后指针到中指针的位置
j = temp;
} else {
// 前指针的值 == 中指针的值,移动前指针到中指针的位置
i = temp;
}
}
return array[min];
}
// 顺序查找
public int find(int[] array,int i,int j){
int min = array[i];
for(;i<=j;i++){
if(array[i]<min){
min = array[i];
}
}
return min;
}
}