面试题11：旋转数组的最小数字
题目要求：
把一个数组最开始的若干个元素搬到末尾成为数组的旋转，如1,2,3,4,5=>3,4,5,1,2；0,1,1,1,1=>1,1,1,0,1；0,1,1,1,1=>1,0,1,1,1。求一个原本递增的数组旋转后的最小数字。
解题思路：
考察二分查找。原本有序，进行了旋转，但在一定程度上还是有序的。有了这个出发点，如果熟悉二分查找应该就离最终结果差不多了。通过观察中间点与左右点的关系，缩小范围，从而找到最小值。缩小范围时要注意值相等的情况，尤其是左右中三个值都相等的情况，这种特殊情况是无法折半缩小范围的，只能逐步缩小，即左右点各缩进一个单位。
此题比较考验逻辑，明白为什么能用二分查找 && 把各个ifelse情况理清楚 -> 解决
package chapter2;
/**
* Created by ryder on 2017/6/28.
* 旋转数组的最小数字
*/
public class P82_MinNumberInRotatedArray {
public static int min(int[] data){
if(data==null || data.length==0)
return -1;
int left = 0;
int right = data.length-1;
int mid;
while(left<right){
mid = left+(right-left)/2;
//left < right
if(data[left]<data[right])
return data[left];
//left > right
else if(data[left]>data[right]){
if(data[mid]>=data[left])
left = mid + 1;
else
right = mid;
}
//left = right
else{
if(data[left]<data[mid])
left = mid + 1;
else if(data[left]>data[mid])
right = mid;
else{
left = left+1;
right = right-1;
}
}
}
return data[right];
}
public static void main(String[] args){
int[] data1 = {3,4,5,1,2};
int[] data2 = {1,0,1,1,1};
int[] data3 = {1,1,1,0,1};
System.out.println(min(data1));
System.out.println(min(data2));
System.out.println(min(data3));
}
}
运行结果
1
0
0
