题解 | #在旋转过的有序数组中寻找目标值#

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

        i = 1
        n = len(nums)
        if n==0:return -1
        elif n==1 and nums[0]!=target:return -1
        while(i<n):
            if nums[i]<nums[i-1]:break
            i+=1
        nums1,nums2 = nums[:i],nums[i:]
        idx1,idx2 = binary_search(nums1,target),binary_search(nums2,target)
        if idx1==-1 and idx2==-1:return -1
        elif idx1>=0:return idx1
        else: return idx2+i

因为这是在AI面试上碰到的题目，所以我没有用任何库函数，尽可能还原面试的真实场景，这个题目的做法是首先找到旋转的位置：这个很简单，就是找破坏递增规则的位置。找到位置之后把数组一分为二，在两个数组中二分查找就可以了，注意边界条件：数组可能是空的和只有1个值的