# 81. Search in Rotated Sorted Array II

## Design

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28202/Neat-JAVA-solution-using-binary-search

## Implementation

class Solution {
public boolean search(int[] nums, int target) {
if (nums.length == 0 || nums == null) return false;

int left = 0, right = nums.length - 1;

while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;

// If left part is sorted
if (nums[mid] > nums[left]) {
if (target < nums[left] || target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
// If right part is rotated
} else if (nums[mid] < nums[left]) {
if (target < nums[mid] || target > nums[right]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// If we get here, that means nums[left] == nums[mid] == nums[right], then shifting out
// any of the two sides won't change the result but can help remove duplicates from
// consideration, here we just use left++ but right-- works too
left++;
}
}

return false;
}
}

## Complexity Analysis

Time: $O(n)$

Space: $O(1)$