Find Minimum in Rotated Sorted Array

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, 5, 6, 7, 0, 1, 2] return 0

Solution

两个要点，第一找好Target 值= num[-1] 第二，要让start 与end向内移动，这样就跟普通的模版方法相反。第一个元素后者最后一个元素为基准线，需要选择最后一个，如果选择第一个元素作为基准线

(1)At the beginning, I use num[mid] to compare num[start] but need to do first detection is if all numbers are all way up and no piviot.

if num[end] > num[start]:

    return num\[start\]

(2) it should be find a target point first , the target point is the last postion of this array.

if we pick up the num[1] as the target point then it won't work for the situation of normal sorted array and the last two items will be the maxium two.

(3) why we do num[mid] <= target, we wanna move the end to left of start as possible as we can so consider the equal belong to <=

(4) make sure the array is null then return 0

(5) There's no case for duplicate.

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