text: from typing import List
  
  #
  # @lc app=leetcode id=33 lang=python3
  #
  # [33] Search in Rotated Sorted Array
  #
  
  # @lc code=start
  
  
  class Solution:
      def search(self, nums: List[int], target: int) -> int:
          low = 0
          high = len(nums) - 1
          while low <= high:
              mid = low + (high - low) // 2
              if nums[mid] == target:
                  return mid
              if nums[low] <= nums[mid]:
                  if target > nums[mid] or target < nums[low]:
                      low = mid + 1
                  else:
                      high = mid - 1
              else:
                  if target < nums[mid] or target > nums[high]:
                      high = mid - 1
                  else:
                      low = mid + 1
          return -1
  
  
  # @lc code=end
  if __name__ == "__main__":
      s = Solution()
      nums = [4, 5, 6, 7, 0, 1, 2]
      print(s.search(nums, 0))
  