2019-05-05LeetCode33. 搜索旋转排序数组

这题的特殊测试用例太多了，很烦

1.[3,1] 1 导致s==e-1的时候并不是找到这个数了
2.[1,3] 0 找不到e-1==s
3.[1] 1 只有一个元素
4.[1,2,3,4] 没有旋转

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if(len(nums)==0 or nums== None):return -1
        s,e=0,len(nums)-1
        if(nums[s]<=nums[e]): # 等号表示特殊情况 s==e 只有一个元素
            return self.Binary(nums,target)
        while(s<e):
            mid=(s+e)//2
            if(nums[mid]==target):return mid
            elif(nums[e]<nums[mid]):s=mid+1  # 不要和s比，因为有可能mid==s
            elif(nums[e]>nums[mid]):e=mid
        if(target>=nums[0]):
            return self.Binary(nums[:e],target)
        else:
            return self.Binary(nums[e:],target,e)
        
    def Binary(self,nums,target,bias=0):
        s,e=0,len(nums)-1
        while(s<=e):
            mid=(s+e)//2
            if(nums[mid]==target):return mid+bias # 偏置要加上
            elif(nums[mid]<target):s=mid+1
            else:e=mid-1
        return -1

简化版本1，没想到稍微慢了十几毫秒

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if(len(nums)==0 or nums== None):return -1
        s,e=0,len(nums)-1

        while(s<e):
            mid=(s+e)//2
            if(nums[mid]==target):return mid
            elif(nums[e]<nums[mid]):s=mid+1  # 不要和s比，因为有可能mid==s
            elif(nums[e]>nums[mid]):e=mid
        if(target>nums[len(nums)-1]):   # 此处跟最后一个比较，是因为e可能是0，所以为了没有旋转的情况
            return self.Binary(nums[:e],target)
        else:
            return self.Binary(nums[e:],target,e)
        
    def Binary(self,nums,target,bias=0):
        s,e=0,len(nums)-1
        while(s<=e):
            mid=(s+e)//2
            if(nums[mid]==target):return mid+bias # 偏置要加上
            elif(nums[mid]<target):s=mid+1
            else:e=mid-1
        return -1