搜索旋转排序数组

• 左<中

（1）target比左小或者target比中大时（比小的都小或者比大的都大）：此时target只可能在[mid, r]中，所以l = mid;
（2）其他，即target比左大并且target比中小时（大小在左和中之间）：此时target只可能在[左 + 1, mid]中，所以 l = l + 1; r = mid;

• 左>中

（1）target比左小并且target比中大时（大小在左和中之间）：此时target只可能在[mid, r]中，所以l = mid;
（2）其他，即target比左大或者比中小时（比大的都大或者比小的都小）：此时target只可能在[左 + 1, mid]中，所以 l = l + 1; r = mid;

class Solution:
    def findnum(self,nums,target,starts,ends):
        if starts>ends:
            return -1
        if nums[(starts+ends)//2]==target:
            return (starts+ends)//2
        if nums[starts]==target:
            return starts
        if nums[ends]==target:
            return ends
        res=-1
        if(nums[(starts+ends)//2]>nums[starts]):
            # 位于前1个数组
            if(target>nums[(starts+ends)//2] or target<nums[starts]):
                res=self.findnum(nums,target,(starts+ends)//2+1,ends)
            # elif(target<nums[(starts+ends)//2] or target>nums[starts]):
            else:
                res=self.findnum(nums,target,starts,(starts+ends)//2-1)
        else:
            # 位于后一个数组
            if(target>nums[starts] or target<nums[(starts+ends)//2]):
                res=self.findnum(nums,target,starts,(starts+ends)//2-1)
            # elif(target<nums[starts] or target>nums[(starts+ends)//2]):
            else:
                res=self.findnum(nums,target,(starts+ends)//2+1,ends)
        # 如果是两个有序递增且无关联数组可以用下面的方法:
        # if(nums[(starts+ends)//2]>target or nums[starts]<target):
        #     res1=self.findnum(nums,target,starts,(starts+ends)//2-1)
        # if(nums[(starts+ends)//2]<target or nums[ends]>target):
        #     res2=self.findnum(nums,target,(starts+ends)//2+1,ends)
        # if res1!=-1:
        #     return res1
        # if res2!=-1:
        #     return res2
        return res
    def search(self, nums: List[int], target: int) -> int:
        starts=0
        ends=len(nums)-1
        if nums[(starts+ends)//2]==target:
            return (starts+ends)//2
        if nums[starts]==target:
            return starts
        if nums[ends]==target:
            return ends
        return self.findnum(nums,target,starts,ends)