分类：BinarySearch
考察知识点：BinarySearch
最优解时间复杂度：O(logn~n)
最优解空间复杂度：O(1)
81. Search in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
This is a follow up problem to Search in Rotated Sorted Array, where
numsmay contain duplicates.Would this affect the run-time complexity? How and why?
代码：
BinarySearch方法:
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
if len(nums)==0:
return False
start=0
end=len(nums)-1
while(end-start)>1:
mid=(end-start)//2+start
if nums[mid]==target or nums[start]==target or nums[end]==target:
return True
if nums[start]<=nums[mid] and nums[mid]>=nums[end]:
start+=1
end-=1
else:
if nums[start]<nums[mid]:
#说明左边单调递增
if nums[start]<=target and target<=nums[mid]:
#说明就在左半边
end=mid
else:
#说明不在左半边
start=mid
else:
if nums[mid]<=target and target<=nums[end]:
start=mid
else:
end=mid
print(start,end)
if nums[start]==target or nums[end]==target:
return True
return False
讨论：
1.这道题是033的升级版，但是由于有重复，需要考虑几种特殊的case。[1,1,1,3,1],3和,[0,0,1,1,2,0],2,那么应该有
if nums[start]<=nums[mid] and nums[mid]>=nums[end]:
start+=1
end-=1
这种缩进的情况
记得考虑特殊情况
