Leetcode-153题: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.

You may assume no duplicate exists in the array.

简单的做法

    顺序扫描一遍

代码

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def findMin(self, nums):
        i = 0
        while i+1 < len(nums) and nums[i+1] > nums[i]:
            i += 1
        if i == len(nums)-1:
            return nums[0]
        return nums[i+1]

二分查找的做法

当nums[m] == nums[l]，此时或者l==r或者r=l+1，直接比较即可；当nums[m] > nums[l]时，左边的最小元素是nums[l]，右边可能有比它小的也可能没有，找出右边最小的与nums[l]比较即可；当nums[m] < nums[l]时，最小元素一定出现在[l,m]中，需包含m。

代码

class Solution(object):

    def search(self, nums, l, r):
        m = l + (r-l)/2
        if nums[m] == nums[l]:
            return min(nums[l],nums[r])
        elif nums[m] > nums[l]:
            return min(nums[l],self.search(nums, m+1, r))
        else:
            return self.search(nums, l, m)

    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums==None or len(nums)==0:
            return None
        return self.search(nums,0,len(nums)-1)