剑指8：寻找旋转数组的最小数字

题目：

把一个有序数组的最开始的若干元素搬到数组末尾对数组进行旋转作为输入，输出该数组的最小元素（或下标）。例如 {3,4,5,1,2} 是 {1,2,3,4,5} 的旋转，该数组的最小值为 1，最小值下标为 3.

思路：

思路非常重要，首先我们都知道在一个有序数组中查找一个元素一般使用二分查找，这道题的数组也是一个有序数组的变体，同样也是寻找一个元素，因此自然而然应该能联想到使用二分查找的思想进行解答。

有了这个思路以后就是具体写代码分析各种情况了，显然不可能和二分查找一模一样，因为旋转数组并不是一个严格的有序数组，而是一个局部有序数组，不过没关系，在纸上写个例子一点点分析。

• 首先任何算法实现都需要考虑边界条件，这里的边界就是空数组（返回-1）、 未旋转数组（返回第一个元素下标）、有重复值数组（全部元素相等）
• 按照二分查找思想，使用 mid 元素与最后一个元素进行比较（不要和第一个元素比），如果 arr[mid] < arr[high]，说明右半边是递增的，那么最小元素肯定在 arr[mid] 的左半部分，值得注意的是此时 mid 这个元素有可能就是最小值，因此在后面的比较中需要包含这个元素
• 如果 arr[mid] > arr[high]，则说明 arr[high] 属于被旋转的一部分，因此最小值肯定在 mid 的右半部分数组了，注意此时 arr[mid] 可以肯定不会是最小值（因为在右半部分比 arr[high] 大），因此可以将 mid 直接排除
• 如果允许有重复数据，则可能会出现 arr[mid] == arr[high] 的情况，此时其实无法判断最小值到底在那一边，参考形如 001111111 这样的数组不同的旋转情况，此时只能逐个遍历
• 最后最小的元素下标即 low

public static int searchMinIndex(int[] arr){
    if (arr==null || arr.length == 0) //边界判空
        return -1;
    int low = 0;
    int high = arr.length - 1;
    while (low < high){  // 利用二分查找思路，但需要结合实际情况
        int mid = (low + high) / 2;
        if (arr[mid] > arr[high]){ // 此时说明最小值在 mid 的右半边数组中，并且 arr[mid] 肯定不是最小值，可以排除
            low = mid + 1;
        } else if (arr[mid] < arr[high]){ // 此时说明有半部分是递增的，最小值在 mid 左边数组中，并且 arr[mid] 此时有可能就是最小值，因此保留
            high = mid;
        } else { // 这种情况根本无法判断到底在左边还是在右边，只能遍历
            high = high - 1;
        }
    }
    return low;
}