Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

Example

Given [4,4,5,6,7,0,1,2] return 0.

Solution

//  这道题目在面试中不会让写完整的程序

//  只需要知道最坏情况下 \[1,1,1....,1\] 里有一个0

//  这种情况使得时间复杂度必须是 O\(n\)

//  因此写一个for循环就好了。

//  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。

//  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。



重复元素出现在pivot 点时候需要考虑动态的删除最后一个元素。

end = end - 1

class Solution:
    # @param num: a rotated sorted array
    # @return: the minimum number in the array
    def findMin(self, num):
        # write your code here
        start, end = 0, len(num) - 1
        while start + 1 < end:
            mid = (start+end)/2
            if num[mid] > num[end]:
                start = mid
            elif num[mid] < num[end]:
                end = mid
            else:
                end = end - 1
        return min(num[start], num[end])