Find Minimum in Rotated Sorted Array -- LeetCode

这道题是Search in Rotated Sorted Array的扩展，差别就是如今不是找一个目标值了，而是在bst中找最小的元素。主要思路还是跟Search in Rotated Sorted Array差点儿相同。还是通过左边界和中间的大小关系来得到左边或者右边有序的信息。假设左半边有序。那么左半边最小就是左边第一个元素，能够和当前最小相比取小的，然后走向右半边。否则，那么就是右半半边第一个元素，然后走向左半边。这样子每次能够截掉一半元素，所以最后复杂度等价于一个二分查找。是O(logn)，空间上仅仅有四个变量维护二分和结果，所以是O(1)。代码例如以下：

public int findMin(int[] num) {
    if(num == null || num.length==0)
        return 0;
    int l = 0;
    int r = num.length-1;
    int min = num[0];
    while(l<r-1)
    {
        int m = (l+r)/2;
        if(num[l]<num[m])
        {
            min = Math.min(num[l],min);
            l = m+1;
        }
        else if(num[l]>num[m])
        {
            min = Math.min(num[m],min);
            r = m-1;
        }
        else
        {
            l++;
        }
    }
    min = Math.min(num[r],min);
    min = Math.min(num[l],min);
    return min;
}

有朋友可能注意到上面的实现还有第三种情况，就是左边界和中间是相等的情况。这道题目事实上是不用发生的，由于元素没有反复。而Find Minimum in Rotated Sorted Array II这道题这考虑了元素反复的情况，这里仅仅是为了算法更加一般性。就把那个情况也包括进来，有兴趣的朋友能够看看Find Minimum in Rotated Sorted Array II对反复元素的分析哈。