寻找排序数组中的最小值

题目要求

解题思路

二分法

代码

class Solution:
    def findMin(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1
        while low < high:
            pivot = low + (high - low) // 2
            if nums[pivot] < nums[high]:
                high = pivot 
            else:
                low = pivot + 1
        return nums[low] 

复杂度分析

时间复杂度：$O(logN)$，在二分查找的过程中，每一步会忽略一般的区间，因此时间复杂度为$O(logN)$
空间复杂度：$O(1)$