33. Search in Rotated Sorted Array

class Solution:
    def search(self, A: List[int], target: int) -> int:
        n = len(A)
        left, right = 0, n - 1

        while left <= right:
            mid = (left + right) // 2
            if A[mid] == target:
                return mid

            if A[left] <= A[mid]:
                if A[left] <= target < A[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if A[mid] < target <= A[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

class Solution:
    def search(self, A: List[int], target: int) -> int:
        n = len(A)
        left, right = 0, n - 1

        while left < right:
            mid = left + (right - left) // 2
            if A[mid] > A[right]:
                left = mid + 1
            else:
                right = mid
        
        pivot = left
        
        if pivot == 0:
            left, right = 0, n - 1
        elif A[0] <= target <= A[pivot - 1]:
            left, right = 0, pivot - 1
        else:
            left, right = pivot, n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if A[mid] < target:
                left = mid + 1
            elif A[mid] > target:
                right = mid - 1
            else:
                return mid

        return -1

class Solution:
    def search(self, A: List[int], target: int) -> int:
        n = len(A)
        left, right = 0, n - 1

        while left <= right:
            mid = left + (right - left) // 2
            
            sameside = (A[0] > A[mid]) == (A[0] > target)
            if sameside:
                v = A[mid]
            else:
                v = -inf if target < A[mid] else inf
            
            if v < target:
                left = mid + 1
            elif v > target:
                right = mid - 1
            else:
                return mid

        return -1