33. Search in Rotated Sorted Array

Difficulty: Medium

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

1. Binary Search

$O(logn)$ runtime,

$O(1)$ space

題目限制

$O(logn)$複雜度，所以想到用binary search，套用binary search模板。

由於條件比較複雜，先討論各種情況。

python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def feasible(mid):
            # sorted array
            if nums[0] <= nums[-1]:
                return target <= nums[mid]
            # rotated array
            else:
                if nums[0] <= target:
                    return target <= nums[mid] or nums[mid] < nums[0]
                else:
                    return target <= nums[mid] < nums[0]
        
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        
        if nums[left] == target:
            return left
        else:
            return -1

簡化版如下。

python

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

討論區的想法很棒，把rotated過的部分視為inf和-inf，參考這篇。

• If target is let's say 14, then we adjust nums to this, where "inf" means infinity:
  • [12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
• If target is let's say 7, then we adjust nums to this:
  • [-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

tags: leetcode