text: """
  
  There is an integer array nums sorted in ascending order (with distinct values).
  Prior to being passed to your function, nums is rotated 
  at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).
  For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
  Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
  You must write an algorithm with O(log n) runtime complexity.
  
  
  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
  
  Example 3:
  
  Input: nums = [1], target = 0
  Output: -1
   
  
  Constraints:
  
  1 <= nums.length <= 5000
  -104 <= nums[i] <= 104
  All values of nums are unique.
  nums is guaranteed to be rotated at some pivot.
  -104 <= target <= 104
  
  """
  # V0
  # IDEA : BINARY SEARCH
  #        -> CHECK WHICH PART IS ORDERING
  #        -> CHECK IF TARGET IS IN WHICH PART
  # CASES :
  #  1) if mid is on the right of pivot -> array[mid:] is ordering
  #     -> check if mid in on the left or right on mid
  #     -> binary search on left or right sub array
  #  2) if mid in on the left of pivot  -> array[:mid] is ordering
  #     -> check if mid in on the left or right on mid
  #     -> binary search on left or right sub array
  ### NOTE : THE NESTED IF ELSE CONDITION 
  class Solution(object):
      def search(self, nums, target):
          if not nums: return -1
          left, right = 0, len(nums) - 1
          while left <= right:
              mid = (left + right) // 2
              if nums[mid] == target:
                  return mid
              #---------------------------------------------
              # Case 1 :  nums[mid:right] is ordering
              #---------------------------------------------
              # all we need to do is : 1) check if target is within mid - right, and move the left or right pointer
              if nums[mid] < nums[right]:
                  # mind NOT use (" nums[mid] < target <= nums[right]")
                  # mind the "<="
                  if target > nums[mid] and target <= nums[right]: # check the relationship with target, which is different from the default binary search
                      left = mid + 1
                  else:
                      right = mid - 1
              #---------------------------------------------
              # Case 2 :  nums[left:mid] is ordering
              #---------------------------------------------
              # all we need to do is : 1) check if target is within left - mid, and move the left or right pointer
              else:
                  # # mind NOT use (" nums[left] <= target < nums[mid]")
                  # mind the "<="
                  if target < nums[mid] and target >= nums[left]:  # check the relationship with target, which is different from the default binary search
                      right = mid - 1
                  else:
                      left = mid + 1
          return -1     
  
  # V1
  # https://blog.csdn.net/fuxuemingzhu/article/details/79534213
  # CHECK ALSO : BINARY SEARCH 
  # https://github.com/yennanliu/CS_basics/blob/master/algorithm/python/binary_search.py
  class Solution(object):
      def search(self, nums, target):
          """
          :type nums: List[int]
          :type target: int
          :rtype: int
          """
          if not nums: return -1
          left, right = 0, len(nums) - 1
          while left <= right:
              mid = (left + right) // 2
              if nums[mid] == target:
                  return mid
              if nums[mid] < nums[right]:
                  if target > nums[mid] and target <= nums[right]: # check the relationship with target, which is different from the default binary search
                      left = mid + 1
                  else:
                      right = mid - 1
              else:
                  if target < nums[mid] and target >= nums[left]:  # check the relationship with target, which is different from the default binary search
                      right = mid - 1
                  else:
                      left = mid + 1
          return -1     
  
  # V1'
  # https://www.jiuzhang.com/solution/search-in-rotated-sorted-array/#tag-highlight-lang-python
  class Solution:
      """
      @param A: an integer rotated sorted array
      @param target: an integer to be searched
      @return: an integer
      """
      def search(self, A, target):
          if not A:
              return -1
              
          start, end = 0, len(A) - 1
          while start + 1 < end:
              mid = (start + end) // 2
              if A[mid] >= A[start]:
                  if A[start] <= target <= A[mid]:
                      end = mid
                  else:
                      start = mid
              else:
                  if A[mid] <= target <= A[end]:
                      start = mid
                  else:
                      end = mid
                      
          if A[start] == target:
              return start
          if A[end] == target:
              return end
          return -1
  
  # V1''
  # https://blog.csdn.net/aliceyangxi1987/article/details/50557496
  class Solution(object):
      def search(self, nums, target):
          """
          :type nums: List[int]
          :type target: int
          :rtype: int
          """
          
          start=0
          end=len(nums)-1
          
          while start<=end:
          
              mid=(start+end)/2
          
              if nums[mid]==target:
                  return mid
                  
              if nums[mid]>=nums[start]:                              # when nums[mid] belongs left ascending array 
          
                  if target>=nums[start] and target<nums[mid]:
                      end=mid-1
                  else:
                      start=mid+1
              
              if nums[mid]<nums[end]:                                 # when nums[mid] belongs left ascending array 
          
                  if target>nums[mid] and target<=nums[end]:
                      start=mid+1
                  else:
                      end=mid-1        
          return -1
  