正文
[算法题] Search in Rotated Sorted Array ii
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目内容
题目来源：LeetCode
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
题目思路
本题难度：medium
这个题目是基于上一道题Search in Rotated Sorted Array改进的。在上一道题当中，nums[start]和nums[mid]的判断中，将<和=是联合在一起进行判断的。在本题当中，假如nums[start]==nums[mid]，那么将start+=1，将start转移到不等的地方。
Python代码class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if nums==[]:
return False
end=len(nums)-1
start=0
while start<=end:
mid=(start+end)/2
if nums[mid]==target:
return True
if nums[mid]>nums[start]:
if nums[start]<=target and target<nums[mid]:
end=mid
else:
start=mid+1
elif nums[mid]<nums[start]:
if nums[end]>=target and nums[mid]<target:
start=mid+1
else:
end=mid
else:
start+=1
return False
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if nums==[]:
return False
end=len(nums)-1
start=0
while start<=end:
mid=(start+end)/2
if nums[mid]==target:
return True
if nums[mid]>nums[start]:
if nums[start]<=target and target<nums[mid]:
end=mid
else:
start=mid+1
elif nums[mid]<nums[start]:
if nums[end]>=target and nums[mid]<target:
start=mid+1
else:
end=mid
else:
start+=1
return False
