33. Search in Rotated Sorted Array

Loading...LeetCode

就是 Binary Search，分类讨论左右的判断条件复杂了些。

Aug 30:

这两个分类判断的基础是：这是个 rotated sorted array，如果它的 sub array 不单调，那就必须包含 max值，而 max值左边的数字一定都小于右边（右边部分的最大值小于左边最小值），所以对于一个 sub array，只要判断两头元素的单调性，就可以确认整个array 的单调。

更新个iterative写法，占用空间少一点。

BS Recursive

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bs(l, r):
            if r < l: return -1
            m = (l+r)//2
            if target == nums[m]: return m
            # 从中间切，左右两边肯定有一边是sorted的
            # 左边是sorted的，并且target也在左边
            if nums[l] <= target < nums[m]: return bs(l, m-1)
            # 右边是sorted的，并且target在右边 / pivot 在右边
            elif nums[m] < target <= nums[r] or nums[m] > nums[r]: return bs(m+1, r)
            # pivot 在左边
            else: return bs(l, m-1)
        
        return bs(0, len(nums)-1)

BS Iterative

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            m = l+(r-l)//2
            if nums[m] == target: return m
            elif nums[l] <= target < nums[m]: r = m-1
            elif nums[m] < target <= nums[r] or nums[m] > nums[r]: l = m+1
            else: r = m-1
                
        return -1