题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路
12345，旋转后 34512，最小值是1，那么用二分查找很容易找到最小值为1:。二分查找部分不再赘述
考虑下特殊情况：
- 12345这个数组，假设我们旋转了0个元素，那么旋转后的结果还是12345，那么二分的时候 left < right 直接就是有序的 不用再进行操作直接返回left即可
- 01111这个数组旋转后变成10111，那么进行二分的时候 mid == left == right == 1，那么left 和 right 哪个下标指向mid呢？如果left = mid 那么就错过最小值0所在的左侧了，这种情况只能 顺序查找了。
题解
public int minNumberInRotateArray(int [] array) {
int n = array.length;
if (n <= 0 ) return 0;
int left = 0;
int right = n-1;
int mid = left;
// left >= right 才循环，否则直接返回
while(array[left] >= array[right]){
// 二分查找结束条件
if (right - left == 1){
mid = right;
break;
}
// 这种 二分写法 可以防止 （left+right）/2 越界
mid = left + (right - left) / 2;
// 特殊情况 left == mid == right 只能顺序查找
if (array[left] == array[right] && array[left] == array[mid]){
// sequence search
return SequenceSearch(array,left,right);
}
// mid 在左侧数列
if (array[left] <= array[mid] ){
left = mid;
}
// mid 在右侧数列
else if(array[right] >= array[mid] ){
right = mid;
}
}
return array[mid];
}
public int SequenceSearch(int []array,int low,int high){
int result = Integer.MAX_VALUE;
for (int i = low; i <= high; i++) {
if(array[i] < result) {
result = array[i];
}
}
return result;
}
