LeeCode 33. 搜索旋转排序数组（法1：寻找下标 k）

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

这是比较容易想到的方法，先寻找下标，再还原数组，然后寻找target索引，再转换索引

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        nums_len = len(nums)
        if nums_len == 1:
            if nums[0] == target:
                return 0
            else:
                return -1

        if nums_len == 0:
            return -1

        # 首先二分法找旋转值
        l, r = 0, nums_len - 1
        
        while l != r - 1:
            mid = (l + r) // 2
            if nums[mid] > nums[l]:
                l = mid
            elif nums[mid] < nums[l]:
                r = mid

        rotate_nums = None
        # print(l, r)
        if l == r -1 and nums[l]>nums[r]:
            # print(l, r)
            rotate_nums = nums[r:] + nums[:l+1]
        else:
            # 如果没有找到，说明在k=0时候旋转，即没有旋转
            l, r = 0, len(nums) - 1

            # 左右指针相邻则退出
            # 不考虑复杂的l=r的情况
            # 且避免了/2时l与r不变化导致的死循环
            while l+1 < r:
                mid = (l + r) // 2

                if nums[mid] == target:
                    return mid
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1

            # 再判断相邻时是否满足
            if nums[l] == target:
                return l

            if nums[r] == target:
                return r

            return -1            

        # left_point(小于left_point则为右边的，否则为左边的)
        left_len = nums_len - l - 1
        rotate_point = l

        print('left_len', left_len)
        print('rotate_point', rotate_point)
        nums = rotate_nums
        print(nums)

        # 直接用二分法
        l, r = 0, nums_len - 1

        # 左右指针相邻则退出
        # 不考虑复杂的l=r的情况
        # 且避免了/2时l与r不变化导致的死循环
        while l+1 < r:
            mid = (l + r) // 2

            if nums[mid] == target:
                print('mid1', mid)

                if mid < left_len:
                    return rotate_point + mid + 1
                else:
                    return mid - left_len

            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1

        # 再判断相邻时是否满足
        if nums[l] == target:
            mid = l

            # print('mid2', mid)

            if mid < left_len:
                return rotate_point + mid + 1
            else:
                return mid - left_len

        if nums[r] == target:
            mid = r

            # print('mid3', mid)

            if mid < left_len:
                return rotate_point + mid + 1
            else:
                # print('mid - left_len', mid - left_len)
                return mid - left_len
        
        return -1