153寻找旋转排序数组中的最小值

题目：

法一：自己的代码

思路：同寻找目标值的索引一样，通过对左端点值右端点值和中间值关系进行分类，如果右边大于左边可直接结束，但右边小于左边还需要继续分类判断

from typing import List
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        res = float('inf')
        while left < right:
            mid = (left + right) >> 1
            if nums[right] < nums[left]:
                # 如果中间值最小，说明[mid,right]为单增区间，所以求最小值后，判断另一个区间[left,mid]
                if nums[mid] < nums[right]:
                    res = min(nums[mid], res)
                    right = mid
                # 否则说明[left, mid]为单增区间，则判断另一个区间[mid+1,right]
                else:
                    res = min(nums[right], res)
                    left = mid + 1
            else:
                # 右边大于左边时，必定为单增区间
                res = min(nums[left], res)
                right = left
        return min(res, nums[left])
if __name__ == '__main__':
    solution = Solution()
    # result = solution.findMin([4,5,6,7,0,1,2])
    result = solution.findMin([4])
    print(result)

View Code

参考别人的改进

思路：不讨论左右端点的关系，直接讨论中间端点和右端点的关系，通过画图容易看出，只要确定二者关系就可以直接确定最小值所在的区间，

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1 
        while left < right:
            mid = left + (right - left) // 2
            if nums[right] < nums[mid]:
                left = mid + 1
            else:
                right = mid 
        return nums[left]
作者：powcai
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/er-fen-by-powcai-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

View Code

ttt

153寻找旋转排序数组中的最小值

推荐阅读