《剑指offer》面试题11：旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
思路：旋转之后的数组实际上可以划分为两个排序的子数组，而且前面子数组的元素都大于或者等于后面子数组的元素。最小的元素刚好是这两个子数组的分界线。可以使用二分查找法的思路来查找这个最小的元素（时间复杂度O(logn)）。初始2个指针分别指向数组的第一个元素和最后一个元素。找到数组的中间元素，如果中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素，此时最小的元素位于该中间元素的后面，把第一个指针指向该中间元素，缩小查找范围，移动之后的第一个指针仍然位于前面的递增子数组。
同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面，把第二个指针指向该中间元素，缩小查找范围，移动之后的第二个指针仍然位于后面的递增子数组。
每次查找范围都会缩小到原来的一半。最终第一个指针会指向前面的递增子数组的最后一个元素，第二个指针会指向后面的递增子数组的第一个元素，也就是它们最终会指向相邻的两个元素，而第二个指针指向的元素就是最小的元素，这就是循环结束的条件。
代码如下：
public static int getMin(int[] arr) {
if (arr == null || arr.length <= 0) {
return 0;
}
int left = 0;
int right = arr.length - 1;
int mid = left;
while (arr[left] >= arr[right]) {
mid = (left + right)/2;
if (arr[left] <= arr[mid]) {
left = mid;
} else if (arr[right] >= arr[mid]) {
right = mid;
}
if (arr[left] == arr[right] && arr[left] == arr[mid]) {
return minInOrder(arr,left,right);
}
if (right - left == 1) {
mid = right;
break;
}
}
return arr[mid];
}
private static int minInOrder(int[] arr,int left,int right) {
int min = arr[left];
for (int i = left + 1;i <= right;i++) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
