from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        low = 0
        high = n - 1

        while low <= high:
            mid = (low + high) // 2

            if nums[mid] == target:
                return mid
            else:
                current = nums[mid]

                # Right part sorted
                if current <= nums[n - 1]:
                    if target <= nums[n - 1]:
                        if current < target:
                            low = mid + 1
                        else:
                            high = mid - 1
                    else:
                        high = mid - 1

                # Left part sorted
                else:
                    if target >= nums[0]:
                        if current < target:
                            low = mid + 1
                        else:
                            high = mid - 1
                    else:
                        low = mid + 1

        return -1