33. Search in Rotated Sorted Array

        """
        1. mid point is pivot point 
        2. mid ptr is between ascending sorted arr ==> how to find lo/hi?? => compare mid ptr with most left and most right [l, mid) and (mid,r]; That says, mid ptr is switching roles as left ptr and right ptr between corresponding sorted sub arrays
        3. within sorted subarray, compare target value with (arr[mid] and arr[l]/arr[r]) 
        
        step1, if arr[mid] == target
        step2, if left is sorted[l, mid) => arr[mid] >= arr[l]
            step2.1 if target within range  [l, mid), r = mid -1 
            step2.2 if not, l = mid 
        step3, if right is sorted[mid,r] => arr[mid]  <= arr[r]
            same above
        """
class Solution:
    def search(self, A: List[int], target: int) -> int:
        #Time O(lgN) space O(1)
        n = len(A)
        l,r = 0,n-1
        while l <= r:
            mid = l + (r-l)//2
            if A[mid] == target:
                return mid
            if A[mid] >= A[l]: # left side is sorted, here = is used because there are cases mid is at position of l; 
                if A[l]<=target<A[mid]:
                    r = mid -1
                else:
                    l = mid+1
            
            elif A[mid] <= A[r]:  # right side is sorted 
                if A[mid]<target<=A[r]:
                    l = mid + 1
                else:
                    r = mid -1
        return -1