在旋转过的有序数组中寻找目标值

描述：有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转，使数组变为[nums[k],nums[k+1],.....,nums[nums.length-1],nums[0],nums[1],.......,nums[k-1]]。 给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），如果不存在请返回-1。

数据范围： 0≤n≤10000，0≤target≤100000 要求：空间复杂度 O(1) ，时间复杂度 O(n)

比如，数组[0,2,4,6,8,10]在下标3处旋转之后变为[6,8,10,0,2,4], 当给定target为10时，10的下标是2，target为3时，nums数组中不存在3，所以返回-1

思路：先找到旋转下标k，查找方法二分查找。因为旋转后，左边部分是升序，右边也升序，所以如果i、j在同一部分，当i < j时，nums[i] < num[j]。而左边部分任意一个值大于右边部分，即如果i、j不属于同一部分，当i < j时，nums[i] > num[j]。而当nums[i] > nums[i+1]时，nums[0:i+1]为左边部分，nums[i+1:len(nums)]为右边部分，即原数组为nums[i+1:len(nums)] + nums[0:i+1]。

将target和nums[0]以及nums[len(nums)-1]进行比较，若target >= nums[0],说明target为左边部分，如果 target <= nums[len(nums)-1] 则target为右边部分，之后用二分查找target在左边或右边部分的位置。若在nums[0]和nums[len(nums)-1]之间则不存在，返回-1

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    @staticmethod
    def halfSearch(arr,left,right,k):
        middle = (int)((left + right) / 2)
        while left < right:
            if arr[middle] == k:
                return middle
            elif arr[left] == k:
                return left
            elif arr[right] == k:
                return right
            elif arr[middle] < k:
                left = middle + 1
            else:
                right = middle - 1
            middle = (int)((left + right) / 2)
        return -1
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        n = len(nums)
        if n == 0:
            return -1
        elif (n == 1) & (nums[0] != target):
            return -1
        elif nums[0] == target:
            return 0
        elif nums[n - 1] == target:
            return (n - 1)
        elif nums[0] < nums[n-1]:
            return self.halfSearch(nums,0,n-1,target)
        left = 0
        right = n - 1
        k = 0
        middle = (int)((left + right) / 2)
        while left < right:
            if nums[middle] > nums[middle + 1]:
                middle = middle + 1
                break
            elif nums[middle] < nums[middle - 1]:
                break
            if nums[middle] > nums[left]:
                left = middle + 1
            elif nums[middle] < nums[right]:
                right = middle - 1
            middle = (int)((left + right) / 2)
        if target >= nums[0]:
            return self.halfSearch(nums,0,middle-1,target)
        elif target <= nums[n-1]:
            return self.halfSearch(nums,middle,n-1,target)
        else:
            return -1