# 81. Search in Rotated Sorted Array II¶

## Information¶

• Diffculty: Medium

• Created: 2020-03-10 08:27:00

• Last Motified: 2020-03-10 08:49:08

• Tags: Array, Binary Search

## Intuition¶

We could use a binary search to check if the target exist in the array.

Generally, if nums[lo] != nums[hi] or nums[lo] == nums[hi] != nums[mid], we could always easily know target should be in nums[lo:mid] or nums[mid:hi]. But if nums[lo] == nums[mid] == nums[hi] (e.g. [1, 1, 1, 3, 1]), there is no way to directly know target is in which part. So in this case, we should both search the left part and the right part.

## Solution¶

```class Solution:
def search(self, nums: List[int], target: int) -> bool:
if not nums:
return False
if nums[0] == target or nums[-1] == target:
return True
return self._helper(0, len(nums) - 1, nums, target)

def _helper(self, lo, hi, nums, target):
if hi - lo <= 1:
return False

mid = (hi + lo) // 2
if nums[mid] == target:
return True
elif nums[lo] == nums[hi] == nums[mid]:
return self._helper(lo, mid, nums, target) or \
self._helper(mid, hi, nums, target)
elif nums[lo] <= nums[mid]:
if nums[lo] <= target <= nums[mid]:
return self._helper(lo, mid, nums, target)
else:
return self._helper(mid, hi, nums, target)
else:
if nums[mid] <= target <= nums[hi]:
return self._helper(mid, hi, nums, target)
else:
return self._helper(lo, mid, nums, target)
```