33. Search in Rotated Sorted Array.md

33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

solution

• 根据rotate的不同，分为两种情况。能用二分是因为可以确保总有一个分支能确保是排序的
• 每种情况分别执行二分搜索

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 左闭右闭. 先决定是那种类型的选择，再决定是在哪一部分
        l = 0
        r = len(nums) - 1  # 因为涉及到nums[r]采用左闭右闭

        while l <= r:
            m = l + (r - l) // 2
            if nums[m] == target:
                return m
            # 先判断mid位于哪半边
            elif nums[m] >= nums[l]:  # mid==left的话，mid确实位于左半边. 这里的=必须与左边判断，如果nums=[3, 1],target=1的话
                if nums[l] <= target < nums[m]:  # 这里的=，之前如果nums[mid]==target已返回，因此二者不可能相等，但是可能等于左边界
                    r = m - 1
                else:
                    l = m + 1
            else:
                if nums[m] < target <= nums[r]:  # 注意这里的=,由于左闭右闭, 因此上面和这里都有=，mid没有是因为最前面等于已返回 
                    l = m + 1
                else:
                    r = m - 1

        return -1

时间复杂度：O(log(n))
空间复杂度：O(1)

follow up

81. Search in Rotated Sorted Array II

153. Find Minimum in Rotated Sorted Array

• 求旋转排序数组最大最小值
  • 最大值：The maximum element is the only element whose next is smaller than it
  • 最大值：如果最大值不是mid或mid+1, 中间大于最后值则最大值位于左边，否则位于右边

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1

        while l < r:  # 必须是小于，不能等于
            m = l + (r - l) // 2
            if nums[m] < nums[r]:  # 和最右判断
                r = m
            else:
                l = m + 1
        return nums[l]

时间复杂度：O(log(n))
空间复杂度：O()

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

154. Find Minimum in Rotated Sorted Array II