旋转数组的最小数字

题目：

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

方案一：遍历

求一个数组中的最小值，最先想到的方法一般都是遍历，然后逐个比较，循环所有元素即可取到最小值。

这种做法是时间复杂度为 O(n) 的方案。

代码：

// O(n) 时间复杂度的方案
public static int iterArray(int[] arr) {

    int min = arr[0];
    for (int num : arr) {
        if (min > num) {
            min = num;
        }
    }

    return min;
}

方案二：二分查找

先拿数组中间的元素和左右两边的元素比较：如果中间位置元素大于左边元素，说明最小元素位于右边，则查找中间-结束 这一段；如果中间位置元素小于左边，说明最小元素位于左边，则查找 开始-中间 这一段。

这种算法时间复杂度是 0(logn)，效率要优于遍历。但实现复杂一些。

代码：

public static int searchArray(int[] arr) {
    int start = 0;
    int end = arr.length - 1;
    int mid = start;

    // 当最左边值大于等于最右边时候开始查找
    // 如果最左边小于最右边，说明没有反转，直接返回第一个元素
    while (arr[start] >= arr[end]) {
        // 如果此时数组只剩下两个数值
        if (end - start == 1) {
            // 最小的就是右边
            mid = end;
            break;
        }
        // 如果数组长度是2个以上
        mid = (start + end) / 2;
        // 假如最左边和中间以及最右边值都相等，只能进行顺序查找，如{1,1,1,0,1}
        if (arr[start] == arr[end] && arr[mid] == arr[start]) {
            return findMinByOrder(arr, start, end);
        }
        if (arr[mid] >= arr[start]) {  
            // 如果最左边小于等于中间，说明最小值在后半部分，把起始位置标记为mid 如{3,4,5,1,2}
            start = mid;
        } else if (arr[mid] <= arr[end]) {
            // 如果最左侧大于等于中间值，说明最小值在前半部分，把结束位置标记为mid 如{5,1,2,3,4}
            end = mid;
        }
    }

    return arr[mid];
}

private static int findMinByOrder(int[] arr, int start, int end) {
    int result = arr[start];
    for (int i = start + 1; i < end; i++) {
        if (result > arr[i]) {
            result = arr[i];
        }
    }
    return result;
}