# Search in Rotated Sorted Array II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/search-in-rotated-sorted-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/search-in-rotated-sorted-array-ii
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo)
---
## Problem
There is an integer array `nums` sorted in non-decreasing order (not necessarily with **distinct** values).

Before being passed to your function, `nums` is **rotated** at an unknown pivot index `k` (`0 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). For example, `[0,1,2,4,4,4,5,6,6,7]` might be rotated at pivot index `5` and become `[4,5,6,6,7,0,1,2,4,4]`.

Given the array `nums` **after** the rotation and an integer `target`, return `true` _if_ `target` _is in_ `nums`_, or_ `false` _if it is not in_ `nums`_._

You must decrease the overall operation steps as much as possible.

**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 similar to [Search in Rotated Sorted Array](/problems/search-in-rotated-sorted-array/description/), but `nums` may contain **duplicates**. Would this affect the runtime complexity? How and why?

# Approaches
## Linear Search
The most straightforward approach is to iterate through each element of the array and check if it matches the target value. This method does not leverage the partially sorted nature of the array.
**Time:** O(N) · **Space:** O(1)
**Pros:** Very simple to understand and implement.; Guaranteed to work correctly for any input array, regardless of its properties.
**Cons:** Highly inefficient, with a time complexity linear to the size of the array.; Fails to utilize the special property of the array (rotated sorted), missing an opportunity for optimization.
### Explanation
This brute-force method involves a simple loop that traverses the array from the first element to the last. In each iteration, it compares the current element with the `target`. If a match is found, the function immediately returns `true`. If the loop completes without finding the target, it means the target is not in the array, and the function returns `false`.

```java
class Solution {
    public boolean search(int[] nums, int target) {
        for (int num : nums) {
            if (num == target) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- 1. Start a loop that iterates from the first element (`index = 0`) to the last element (`index = nums.length - 1`).
- 2. In each iteration, get the current element `nums[i]`.
- 3. Compare the current element with the `target`.
- 4. If `nums[i] == target`, the target is found. Return `true`.
- 5. If the loop finishes without finding any match, return `false`.

## Modified Binary Search
A more optimized approach uses a modified binary search algorithm. The standard binary search is adapted to handle the rotation and the presence of duplicates. The core idea is to identify a sorted subarray in each step and decide whether to search in that half or the other.
**Time:** Average: O(log N), Worst: O(N) · **Space:** O(1)
**Pros:** Much more efficient than linear search on average, with O(log N) time complexity for many cases.; Uses constant extra space.
**Cons:** The worst-case time complexity degrades to O(N) when the array is filled with duplicates, making it no better than linear search in those specific scenarios.; The logic is more complex to implement and reason about compared to linear search.
### Explanation
This approach uses two pointers, `left` and `right`, to define the current search space. In each step, we calculate the middle element `mid`. The main challenge introduced by duplicates is the case where `nums[left] == nums[mid] == nums[right]`. In this scenario, we cannot determine which half is sorted. For example, in `[1, 0, 1, 1, 1]` and `[1, 1, 1, 0, 1]`, `nums[left]`, `nums[mid]`, and `nums[right]` are all `1`. In the first case, the pivot is on the right; in the second, it's on the left. Since we can't make an informed decision, we shrink the search space by incrementing `left` and decrementing `right`. This handles the ambiguity at the cost of a potential O(N) worst-case runtime.

In other cases, at least one half of the array (from `left` to `mid` or `mid` to `right`) must be sorted. We check if `nums[left] <= nums[mid]`. If true, the left half is sorted. We then check if the `target` lies within this sorted range. If it does, we search in the left half (`right = mid - 1`); otherwise, we search in the right half (`left = mid + 1`). If the left half is not sorted (`nums[left] > nums[mid]`), then the right half must be. We apply similar logic to search in the right half.

```java
class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return true;
            }

            // Handle the case of duplicates where we can't decide
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
                continue;
            }

            // Check if the left half is sorted
            if (nums[left] <= nums[mid]) {
                // Target is in the sorted left half
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } 
            // Otherwise, the right half must be sorted
            else {
                // Target is in the sorted right half
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- 1. Initialize pointers `left = 0` and `right = nums.length - 1`.
- 2. Loop as long as `left <= right`.
- 3. Calculate `mid = left + (right - left) / 2`.
- 4. If `nums[mid] == target`, return `true`.
- 5. If `nums[left] == nums[mid] && nums[mid] == nums[right]`, we cannot determine the sorted half. Shrink the search space by doing `left++` and `right--` and continue to the next iteration.
- 6. Check if the left part (`nums[left]` to `nums[mid]`) is sorted (`nums[left] <= nums[mid]`).
- 7. If it is, check if `target` is in the range `[nums[left], nums[mid])`.
- 8. If yes, search in the left half: `right = mid - 1`.
- 9. If no, search in the right half: `left = mid + 1`.
- 10. If the left part is not sorted, the right part (`nums[mid]` to `nums[right]`) must be.
- 11. Check if `target` is in the range `(nums[mid], nums[right]]`.
- 12. If yes, search in the right half: `left = mid + 1`.
- 13. If no, search in the left half: `right = mid - 1`.
- 14. If the loop terminates, the target was not found. Return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] > nums[r]) {
        if (nums[l] <= target && target <= nums[mid]) {
          r = mid;
        } else {
          l = mid + 1;
        }
      } else if (nums[mid] < nums[r]) {
        if (nums[mid] < target && target <= nums[r]) {
          l = mid + 1;
        } else {
          r = mid;
        }
      } else {
        --r;
      }
    }
    return nums[l] == target;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {boolean} */ var search =
  function (nums, target) {
    let [l, r] = [0, nums.length - 1];
    while (l < r) {
      const mid = (l + r) >> 1;
      if (nums[mid] > nums[r]) {
        if (nums[l] <= target && target <= nums[mid]) {
          r = mid;
        } else {
          l = mid + 1;
        }
      } else if (nums[mid] < nums[r]) {
        if (nums[mid] < target && target <= nums[r]) {
          l = mid + 1;
        } else {
          r = mid;
        }
      } else {
        --r;
      }
    }
    return nums[l] === target;
  };

```

### Python

```python
class Solution : def search ( self , nums : List [ int ], target : int ) -> bool : if not nums : return False i = 0 # left pointer j = len ( nums ) - 1 # right pointer while i <= j : mid = ( i + j ) // 2 if nums [ mid ] == target : return True if nums [ i ] <= nums [ mid ]: # left half ordered, right half not ordered if nums [ i ] <= target <= nums [ mid ]: j = mid else : i += 1 else : # right half ordered, left half not ordered if nums [ mid ] <= target <= nums [ j ]: i = mid else : j -= 1 return False ############ class Solution : def search ( self , nums : List [ int ], target : int ) -> bool : l , r = 0 , len ( nums ) - 1 while l <= r : mid = ( l + r ) >> 1 if nums [ mid ] == target : return True if nums [ mid ] < nums [ r ] or nums [ mid ] < nums [ l ]: if target > nums [ mid ] and target <= nums [ r ]: l = mid + 1 else : r = mid - 1 elif nums [ mid ] > nums [ l ] or nums [ mid ] > nums [ r ]: if target < nums [ mid ] and target >= nums [ l ]: r = mid - 1 else : l = mid + 1 else : r -= 1 return False
```

### CPP

```cpp
class Solution {
public:
  bool search(vector<int> &nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] > nums[r]) {
        if (nums[l] <= target && target <= nums[mid]) {
          r = mid;
        } else {
          l = mid + 1;
        }
      } else if (nums[mid] < nums[r]) {
        if (nums[mid] < target && target <= nums[r]) {
          l = mid + 1;
        } else {
          r = mid;
        }
      } else {
        --r;
      }
    }
    return nums[l] == target;
  }
};

```