旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转，该数组的最小值为 1。

最简单的方法就是直接扫描一遍数组，找到数组中最小的数字，这样做它的时间复杂度是
#card=math&code=O%28n%29&height=20&width=36)

观察到最小值在第一部分和第二部分的分界处，且在第二部分，另外可以观察到，由于第二部分是数组的前半部分搬到末尾的，所以第二部分中的值是小于等于第一部分中的值。

对于顺序查找问题，我们可以使用二分查找法。我们使用两个指针分别指向第一部分的开头和第二部分的结尾，然后将这两个值与数组中间的值进行比较，如果中间的值比第一部分的开头大，说明中间的值还在第一部分，我们将第一部分的开头指针移动到中间；同理，如果中间值比第二部分末尾的值小，则中间的值还在第二部分，则将第二部分末尾的指针移动到中间。以此类推，直到两个指针相差一个距离，则到了分界处，取第二部分指针所对应的值，该值即为最小值。图示如下：

但是上面的方法却又一个特例，即中间值与两个指针所指的值相等时，则无法知道如何移动指针

上面两个数组都是 {0, 1, 1, 1, 1} 的旋转，并且中间的值与两个指针指向的值相同，但是中间值一个在第一部分，一个在第二部分，所以我们这时是无法知道如何移动指针，碰到这种情况，我们只能顺序查找了，代码如下

public class Min {
    public static int min(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        int mid = 0;
        // 如果 start 的值小于 end，说明数组没有进行旋转，则返回数组的第一个值，这就是 mid = 0 的原因
        while (arr[start] >= arr[end]) {
            // 如果两个指针相差 1 个距离，则返回第二个指针指向的值
            if (end - start == 1) {
                mid = end;
                break;
            }
            mid = (start + end) / 2;
            // 如何中间的值和两个指针的值相等，则进行顺序查找
            if (arr[start] == arr[end] && arr[start] == arr[mid]) {
                return minInOrder(arr, start, end);
            }
            // 如果中间的值比 start 的值大，则将 start 移至中间
            if (arr[mid] >= arr[start]) {
                start = mid;
            } else if (arr[mid] < arr[end]) {
                // 否则中间的值比 end 小，则将 end 移至中间
                end = mid;
            }
        }
        return arr[mid];
    }
    // 顺序查找的代码
    public static int minInOrder(int[] arr, int start, int end) {
        int minResult = arr[start];
        for (int i = start; i <= end; i++) {
            if (minResult > arr[i]) {
                minResult = arr[i];
            }
        }
        return minResult;
    }
    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 1, 2};
        System.out.println(min(arr)); // 1
    }
}