from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while high >= low:
            mid = (low + high) // 2
            mid_num = nums[mid]
            if target == mid_num:
                return mid

            # 左右至少有一侧为有序
            if nums[0] <= mid_num:  # 不重复保证了，只要条件符合那么这一侧就是有序的
                if nums[low] <= target < mid_num: # target在左侧
                    high = mid - 1
                else: # target在右侧
                    low = mid + 1
            else:
                if mid_num < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return -1


sol=Solution()
# index=sol.search([4,5,6,7,0,1,2], 6)
# print(index)
# index=sol.search([4,5,6,7,0,1,2], 6.5)
# print(index)
# index=sol.search([4,5,6,7,0,1,2], 0)
# print(index)
# index=sol.search([4,5,6,7], 0)
# print(index)
# index=sol.search([4,5,6,7], 4)
# print(index)
# index=sol.search([4,5,6,7], 5)
# print(index)
# index=sol.search([4,5,6,7], 6)
# print(index)
# index=sol.search([4,5,6,7], 7)
# print(index)
index=sol.search([5,1,3], 3)
print(index)