- 左<中
（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)
