旋转数组的最小数字

《剑指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;
}