Leetcode # 81. Search in Rotated Sorted Array II

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

Solution

Leetcode # 33. Search in Rotated Sorted Array 的 solution
配合題目修改了 input 跟 output

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

nums從 ascending order 變為 non-decreasing order
所以針對下列兩種情況進行修改

1. nums[left] == nums[mid] == nums[right]
   此時無法進行下一步的 binary search
   分別對子序列 nums[left + 1: mid] 和 nums[mid + 1: right] 執行 search
   這導致了 time complexity 最壞情況為 O(len(nums))
2. 本來只有 left == mid == right 時，nums[mid] == nums[right] 才會發生
   但現在nums是 non-decreasing order
   因應此變化修正了 nums[mid] < nums[left] and nums[mid] <= nums[right]

Time Complexity:
n := len(nums)
Best Case: O(log(n))
Worst Case: O(n)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def search(self, nums: List[int], target: int, left=0, right=-1) -> bool:
    right += len(nums) if right < 0 else 0
    while left <= right:
      mid = (left + right) // 2
      print(f"{left}: {nums[left]}, {mid}: {nums[mid]}, {right}: {nums[right]}")
      if target == nums[mid]:
        return True
      if nums[left] == nums[mid] == nums[right]:
        return False if right- left <= 2 else \
               (self.search(nums, target, left + 1, mid) \
                or self.search(nums, target, mid + 1, right))
      elif nums[mid] < nums[left] and nums[mid] <= nums[right]:
        if nums[mid] < target <= nums[right]:
          left  = mid + 1
        else:
          right = mid - 1
      # nums[mid] >= nums[left]
      else:
        if nums[left] <= target <= nums[mid]:
          right = mid - 1
        else:
          left  = mid + 1
          
    return False

Last Updated on 2023/08/16 by A1go