text: #%%
  """
  - Search in Rotated Sorted Array
  - https://leetcode.com/problems/search-in-rotated-sorted-array/
  - Medium
  
  Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
  
  (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
  
  You are given a target value to search. If found in the array return its index, otherwise return -1.
  
  You may assume no duplicate exists in the array.
  
  Your algorithm's runtime complexity must be in the order of O(log n).
  
  Example 1:
  
  Input: nums = [4,5,6,7,0,1,2], target = 0
  Output: 4
  Example 2:
  
  Input: nums = [4,5,6,7,0,1,2], target = 3
  Output: -1
  """
  
  
  #%%
  class S1:
      def search(self, nums, target):
          if target in nums:
              return nums.index(target)
          else:
              return -1
  
  #%%
  class S2:
      def search(self, nums, target):
          """
          :type nums: List[int]
          :type target: int
          :rtype: int
          """
          l, r = 0, len(nums) - 1
          while l <= r:
              mid = l + ((r-l) >> 2)
              if nums[mid] == target:
                  return mid
              if nums[mid] < nums[r]:
                  if nums[mid] < target <= nums[r]:
                      l = mid + 1
                  else:
                      r = mid - 1
              else:
                  if nums[l] <= target < nums[mid]:
                      r = mid - 1
                  else:
                      l = mid + 1
          return -1
  