题目描述：

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.

题目大意：

假设一个排好序的数组在某处执行了一次“旋转”，找出最小的元素（数组元素不重复）

解题思路：

二分法（ 复杂度O(logn) ），实测数据比较水，线性枚举（ 复杂度O(n) ）也可以。

Python代码：

二分法（20160523增补，感谢网友null122提醒）：

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low, high = 0, len(nums) - 1
        while low < high:
            mid = (low + high) / 2
            if nums[mid] <= nums[high]: #min位于左侧上升沿
                high = mid
            else: #min位于左侧上升沿与右侧上升沿之间
                low = mid + 1
        return nums[low]

二分法（原始版本）：

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        ans = num[0]
        size = len(num)
        low, high = 0, size - 1
        while low <= high:
            mid = (low + high) / 2
            if num[mid] <= num[high]: #min位于左侧上升沿
                high = mid - 1
            else: #min位于左侧上升沿与右侧上升沿之间
                low = mid + 1
            ans = min(ans, num[mid])
        return ans

线性枚举：

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        return min(num)

 

本文链接：http://bookshadow.com/weblog/2014/10/16/leetcode-find-minimum-rotated-sorted-array/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码