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?

Difficulty: interview

Starter code:

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        

Solutions:
class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         return target in nums


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         l,r = 0, len(nums) -1
         while l <= r:
             m = l+(r-l)//2
             if nums[m] == target: return True
             while nums[m] == nums[l] and l < m:
                 l += 1
             
             if nums[l] <= nums[m]:#[l,m] is sorted
                 if nums[l] <= target < nums[m]:
                     r = m - 1
                 else:
                     l = m+1
             else:
                 if nums[m] < target <= nums[r]:
                     l = m + 1
                 else:
                     r = m - 1
         return False


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         low = 0
         high = len(nums)-1
         while low<=high:
             mid = (low+high)//2
             if nums[mid]==target:
                 return True
             if nums[low]<nums[mid]:
                 if nums[low]<=target and nums[mid]>target:
                     high = mid-1
                 else:
                     low= mid+1
             elif nums[low]>nums[mid]:
                 if nums[mid]<target and nums[high]>=target:
                     low= mid+1
                 else:
                     high = mid -1
             else:
                 low+=1
         return False


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         left, right = 0, len(nums)-1
         while left <= right:
             mid = (left+right) // 2
             if nums[mid] == target:
                 return True
             elif nums[mid] > nums[left]:
                 if target >= nums[left] and target < nums[mid]:
                     right = mid
                 else:
                     left = mid + 1
             elif nums[mid] < nums[left]:
                 if target > nums[mid] and target <= nums[right]:
                     left = mid + 1
                 else:
                     right = mid
             else:
                 left = left + 1
                 
         return False

class Solution:
     res = False
     
     def searchR(self, nums, target, start, end):
         if(start > end or self.res == True):
             return self.res
         else:
             mid = int((start + end) / 2)
             print("Mid index: %d, Mid val: %d, Target: %d" % (mid, nums[mid], target))
             if(nums[mid] == target):
                 self.res = True
             elif(nums[start] <= nums[mid]):
                 if(nums[mid] == nums[end]):
                     self.searchR(nums, target, start, mid - 1)
                     self.searchR(nums, target, mid+1, end)
                 elif (target >= nums[start] and target <= nums[mid]):
                     self.searchR(nums, target, start, mid - 1)
                 else:
                     self.searchR(nums, target, mid+1, end)
             else:
                 print("Here")
                 if (target >= nums[mid] and target <= nums[end]):
                     self.searchR(nums, target, mid + 1, end)
                 else:
                     self.searchR(nums, target, start, mid - 1)
             return self.res
     
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         res = self.searchR(nums, target, 0, (len(nums) - 1))
         return res

class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         
         return self.bsearch(nums, target, 0, len(nums)-1)
         
     
     def bsearch(self, nums, target, left, right):
         
         if left > right:
             return False
         
         mid = (left+right)//2
         if nums[mid] == target:
             return True
         
         #print(nums[left], nums[mid], nums[right])
         if nums[left] < nums[mid]: # left sorted
             
             if nums[left] <= target <= nums[mid]:
                 return self.bsearch(nums, target, left, mid-1)
             else:
                 return self.bsearch(nums, target, mid+1, right)
         
         elif nums[mid] < nums[right]: # right sorted
             
             if nums[mid] <= target <= nums[right]:
                 return self.bsearch(nums, target, mid+1, right)
             else:
                 return self.bsearch(nums, target, left, mid-1)
         
         elif nums[mid] == nums[left]:
             return self.bsearch(nums, target, left+1, right)
         
         elif nums[mid] == nums[right]:
             return self.bsearch(nums, target, left, right-1)
         
         
             


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         if not nums:
             return False
         left, right = 0, len(nums) - 1
         while nums[left] == nums[right] and left != right:
             right -= 1
         while left <= right:
             mid = (left + right) // 2
             if nums[mid] == target:
                 return True
             elif nums[mid] >= nums[left]:
                 if target >= nums[left] and target < nums[mid]:
                     right = mid - 1
                 else:
                     left = mid + 1
             else:
                 if target > nums[mid] and target <= nums[right]:
                     left = mid + 1
                 else:
                     right = mid - 1
         return False

class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         start, end = 0, len(nums)-1
         while start<=end:
             mid = start+(end-start)//2
             if nums[mid]==target:
                 return True
             while start<=end and nums[start]==nums[end]:
                 if nums[start]==target:
                     return True
                 start += 1
                 end -= 1
             if start>end:
                 return False
             if nums[start]<nums[end]:
                 #normal
                 if target<nums[mid]:
                     end = mid-1
                 else:
                     start = mid+1
             else:
                 if nums[mid]<nums[start]:
                     #peak between start and mid
                     if target<nums[mid] or target>=nums[start]:
                         end = mid-1
                     else:
                         start = mid+1
                 else:
                     #peak between mid and end
                     if target>nums[mid] or target<=nums[end]:
                         start = mid+1
                     else:
                         end = mid-1
         return False


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         if not nums:
             return False
         l, r = 0, len(nums)-1
         while l < r:
             mid = (l + r) // 2
             if nums[mid] == target:
                 return True
             if nums[mid] < nums[r]:
                 if nums[mid] < target <= nums[r]:
                     l = mid + 1
                 else:
                     r = mid - 1
             elif nums[mid] > nums[r]:
                 if nums[l] <= target < nums[mid]:
                     r = mid - 1
                 else:
                     l = mid + 1
             else:
                 r -= 1
         return nums[l] == target

class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         if not nums:
             return False
         l = 0
         r = len(nums) - 1
         print((">", l, r))
         while l < r and nums[l] == nums[r]:
             l = l + 1
         while l <= r:
             mid = int((l + r + 1) / 2)
             if target == nums[mid]:
                 return True
             if target < nums[mid]:
                 if target == nums[l]:
                     return True
                 elif target > nums[l]:
                     r = mid - 1
                 elif target < nums[l]:
                     if nums[l] <= nums[mid]:
                         l = mid + 1
                     elif nums[l] > nums[mid]:
                         r = mid - 1
             if target > nums[mid]:
                 if target == nums[r]:
                     return True
                 elif target > nums[r]:
                     if nums[mid] >= nums[l]:
                         l = mid + 1
                     elif nums[mid] < nums[l]:
                         r = mid - 1
                 elif target < nums[r]:
                     l = mid + 1
         return False
             
                     


class Solution:
     def recursive(self, nums, left, right , target):
         print((left, right))
         if left > right:
             return False
         if left == right:
             return nums[left] == target
         if left + 1 == right:
             return nums[left] == target or nums[right] == target
         mid = (left + right) // 2
         if nums[mid] == target:
             return True
         if nums[mid] == nums[left] and nums[mid] == nums[right]:
             return self.recursive(nums, mid, right, target) or self.recursive(nums, left, mid, target)
         else:
             if nums[mid] < target:
                 if nums[right] >= target or (nums[left] <= nums[mid] and nums[mid] >= nums[right]):
                     return self.recursive(nums, mid, right, target)
                 else:
                     return self.recursive(nums, left, mid, target)
             else:
                 if nums[left] <=target or (nums[right] >= nums[mid] and nums[mid] <= nums[left]):
                     return self.recursive(nums, left, mid, target)
                 else:
                     return self.recursive(nums, mid, right, target)
             
             
         
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         return self.recursive(nums, 0, len(nums) - 1, target)


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         if len(nums) == 0:
             return False
         def binary_search(leftIndex, rightIndex):
             midIndex = int((rightIndex+leftIndex)/2)
             if nums[midIndex] == target:
                 return True
             if leftIndex > rightIndex:
                 return False
             return binary_search(leftIndex, midIndex-1) or binary_search(midIndex+1, rightIndex)
         return binary_search(0, len(nums)-1)


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         l, r = 0, len(nums) - 1
         while l <= r:
             mid = l + (r - l)//2
             
             if nums[mid] == target:
                 return True
             
             while nums[mid] == nums[r]:
                 r -= 1
                 mid = l + (r - l)//2
                 if r < 0:
                     return False
             
             if nums[mid] == target:
                 return True
             
             if nums[mid] <= nums[r]:
                 if target > nums[mid] and target <= nums[r]:
                     l = mid + 1
                 else:
                     r = mid - 1
             else:
                 if target < nums[mid] and target >= nums[l]:
                     r = mid - 1
                 else:
                     l = mid + 1
 
             
         return False

class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         if (not nums):
             return False
         i = 0
         while (i + 1 < len(nums) and nums[i] == nums[i + 1]):
             i += 1
         if (i + 1 == len(nums)):
             # nums中所有元素相等
             return nums[0] == target
         
         # 找到最大元素的位置
         l, r = i, len(nums) - 1
         while (l + 1 < r):
             mid = l + (r - l) // 2
             if (nums[i] < nums[mid]):
                 l = mid
             else:
                 r = mid - 1
         highest_pos = l if (nums[l] > nums[r]) else r
         
         if (target >= nums[0]):
             return self._binarySearch(nums, 0, highest_pos, target)
         else:
             return self._binarySearch(nums, highest_pos + 1, len(nums) - 1, target)
         
         
     def _binarySearch(self, nums, l, r, target):
         while (l <= r):
             mid = l + (r - l) // 2
             if (nums[mid] < target):
                 l = mid + 1
             elif (nums[mid] > target):
                 r = mid - 1
             else:
                 return True
         return False


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: bool
         """
         for i in nums:
             if i == target:
                 return True
             
         return False