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 nums may contain duplicates. Would this affect the run-time complexity? How and why?
My code:
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
index=self.find_target(nums,0,len(nums),target)
if index==-1:
return False
else:
return True
def find_target(self,nums,i,j,target):
if i>j:
return -1
if j-i<=2:
for k in range(i,j):
if nums[k]==target:
return k
return -1
medium=nums[int((i+j)/2)]
medium_index=int((i+j)/2)
print('get i %d, j %d with medium %d'%(i,j,medium))
if medium==target:
return int((i+j)/2)
label1=self.find_target(nums,medium_index+1,j,target)
label2=self.find_target(nums,i,medium_index,target)
if label1!=-1:
return label1
elif label2!=-1:
return label2
return -1
Solution: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/