Search in Rotated Sorted Array II

You are given an integer array nums sorted in ascending order (not necessarily distinct values), and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,4,4,5,6,6,7] might become [4,5,6,6,7,0,1,2,4,4]).

If target is found in the array return its index, otherwise, return -1.

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

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums is guaranteed to be rotated at some pivot.
• -104 <= target <= 104

Follow up: This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the run-time complexity? How and why?

Analysis:

一开始想二分法找pivot point，然后再找target。

improve：

直接一次二分法找target，根据mid和r的对比来看哪边是sorted。

如果中间数比left一样大，我们无法分辨哪边是sorted，那我们直接left+=1

如果中间数≤right，(或者<left)则说明右边是sorted，然后看target在不在右边，不然就是在左边。

如果中间数>left, or > right则说明左边是sorted，然后看target在不在左边，不然就是在右边。

Solution：

def search(self, nums, target):
 “””
 :type nums: List[int]
 :type target: int
 :rtype: bool
 “””
 i, j = 0, len(nums)-1
 
 while i<=j:
   mid = (i+j)/2
   if nums[mid] == target: return True
 
   if nums[i] == nums[mid]:
     i += 1
 
   elif nums[mid] <= nums[j]:
     if nums[mid] < target and target <= nums[j]:
       i = mid + 1
     else:
       j = mid — 1
   else:
     if nums[mid] > target and target >= nums[i]:
       j = mid — 1
     else:
       i = mid + 1
 
 return False