题解 | #旋转数组的最小数字#

这道题花了蛮长的时间，明确知道使用二分法，但是在决策：什么时候当下的mid是最小值？选择左边还是右边？这两个最为纠结。
考虑两种情况：
一种是顺序的：[1, 2, 3, 4, 5, 6] 分成两部分[1, 2, 3] 4 [5, 6]
一种是翻转的：[6, 1, 2, 3, 4, 5] 分成两部分[6, 1, 2] 3 [4, 5]
可以看到，咱们虽然看不到区间内最小的值，例如[6, 1, 2]最小为1，但是6到2之间一定小于3，肯定包含比3小的数，例如2，所以选择端点小的区间就可以解决“选择左边还是右边”的问题。
[1, 2, 3]最小的端点是1，小于4；
[6, 1, 2]最小的端点是2，小于3;
那么同样的，如果mid的值小于左边也小于右边的值，则中间mid是最小的，直接返回。

上面的方式忽略掉了一个问题，踩到了最大的坑，就是重复值问题：
[5,1,2,2,2,3] 分拆为两部分：[5,1,2] 2 [2,3]，这时候无论你选择直接返回2还是选择左右两边都是有问题的。
个人的做法是，在选择好mid值之后，分拆左右两边的时候会左右移动去除重复值，上述例子拆为[5,1] 2 [3]。
所以极限情况下会将时间复杂度为On。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        return find(array, 0, array.length - 1);
    }

    private int find(int []array, int begin, int end) {
        if (begin == end) {
            return array[begin];
        }
        int mid = (end + begin) / 2;
        int midValue = array[mid];

        int leftBegin = begin;
        int leftEnd = Math.max(begin, mid - 1);
        while(leftEnd - 1 >= begin) {
            if(array[leftEnd] == midValue) {
                leftEnd--;
            } else {
                break;
            }
        }
        int leftMin = Math.min(array[leftBegin], array[leftEnd]);

        int rightBegin = Math.min(end, mid + 1);
        while(rightBegin + 1 <= end) {
            if(array[rightBegin] == midValue) {
                rightBegin++;
            } else {
                break;
            }
        }
        int rightEnd = end;
        int rightMin = Math.min(array[rightBegin], array[rightEnd]);
        if (midValue < leftMin && midValue < rightMin) {
            return midValue;
        }
        if (leftMin < rightMin) {
            return find(array, leftBegin, leftEnd);
        } else {
            return find(array, rightBegin, rightEnd); 
        }      
    }
}