Leetcode # 33. Search in Rotated Sorted Array

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

      # when (right - left) == 1, mid == left
      elif nums[mid] >= nums[left] and nums[mid] > nums[right]:
        if target < nums[mid] and target >= nums[left]:
          right = mid - 1
        else:
          left  = mid + 1
      elif nums[mid] < nums[left] and nums[mid] < nums[right]:
        if target > nums[mid] and target <= nums[right]:
          left  = mid + 1
        else:
          right = mid - 1

      # nums[mid] >= nums[left] and nums[mid] < nums[right]    
      else:
        if target < nums[mid]:
          right = mid - 1
        else:
          left  = mid + 1
    return -1

 

合併 case 1: nums[mid] >= nums[left] and nums[mid] > nums[right]
和 case 3: nums[mid] >= nums[left] and nums[mid] < nums[right]

# nums[mid] >= nums[left]
else:
  if (target < nums[mid] and target >= nums[left] and nums[mid] > nums[right]) \
      or (target < nums[mid] and nums[mid] < nums[right]):
    right = mid - 1
  else:
    left  = mid + 1

提出target < nums[mid]

      # nums[mid] >= nums[left]
      else:
        if target < nums[mid] \
            and ((target >= nums[left] and nums[mid] > nums[right]) \
                 or nums[mid] < nums[right]):
          right = mid - 1
        else:
          left  = mid + 1

→ if	target > nums[mid]
	or ( ):	(target < nums[left] or nums[mid] <= nums[right]) and (nums[mid] >= nums[right])
		left = mid + 1

其 else: 的條件
≡ if target < nums[mid] and (target >= nums[left] or nums[mid] <= nums[right]): right = mid – 1
拆開後可以得到兩個條件：
a. nums[left] <= target < nums[mid] or 
b. target < nums[mid] and nums[mid] <= nums[right]

target < nums[mid] and nums[mid] <= nums[right]
加上原本的nums[mid] >= nums[left]
→ b1. target < nums[mid] and b2. nums[left] <= ]nums[mid] <= nums[right]
b2. 表示 left, mid, right 都在 numsA ⇒ target >= nums[left]
故 a. 和 b. 闡述的是同一個條件
⇒ a. nums[left] <= target < nums[mid] or 
b. target < nums[mid] and nums[mid] <= nums[right]
只保留 a.

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

 

Solution: Find num₀ + Search (Do Binary Search Twice)

num₀ ≡ the smallest element

Time Complexity: O(2 * log(n)) = O(log(n))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)