304 North Cardinal St.
Dorchester Center, MA 02124

# Search in Rotated Sorted Array II LeetCode Solution

## Problem – Search in Rotated Sorted Array II LeetCode Solution

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, nums, ..., 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, but `nums` may contain duplicates. Would this affect the runtime complexity? How and why?

## Search in Rotated Sorted Array II LeetCode Solution in Python

``````# If the length of the given array list is 1, then check the first element and return accordingly
if len(nums)==1:
if nums!=target:
return False
else:
return True

left=0
right=len(nums)-1
# binary search
while(left<=right):

# shifting to remove duplicate elements
while left<right and nums[left] == nums[left+1]:
left+=1
while left<right and nums[right] == nums[right-1]:
right-=1

# step 1 calculate the mid
mid=(left+right)//2

#step 2
if nums[mid]==target:
return True

#step 3
elif nums[left]<=nums[mid]:
if nums[mid]>=target and nums[left]<=target:
right=mid-1
else:
left=mid+1

# step 4
else:
if target>=nums[mid] and target<=nums[right]:
left=mid+1
else:
right=mid-1

# step 5
return False

``````

## Search in Rotated Sorted Array II LeetCode Solution in C++

``````class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;

while(l <= r)
{
int mid = l + (r-l) / 2;
if (nums[mid] == target)
return true;
// with duplicates we can have this contdition, just update left & right
if((nums[l] == nums[mid]) && (nums[r] == nums[mid]))
{
l++;
r--;
}
// first half
// first half is in order
else if(nums[l] <= nums[mid])
{
// target is in first  half
if((nums[l] <= target) && (nums[mid] > target))
r = mid - 1;
else
l = mid + 1;
}
// second half
// second half is order
// target is in second half
else
{
if((nums[mid] < target) && (nums[r]>= target))
l = mid + 1;
else
r = mid - 1;
}
}
return false;
}
};
``````

## Search in Rotated Sorted Array II LeetCode Solution in Java

``````    public boolean search(int[] nums, int target) {
int start = 0, end = nums.length - 1, mid = -1;
while(start <= end) {
mid = (start + end) / 2;
if (nums[mid] == target) {
return true;
}
//If we know for sure right side is sorted or left side is unsorted
if (nums[mid] < nums[end] || nums[mid] < nums[start]) {
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
//If we know for sure left side is sorted or right side is unsorted
} else if (nums[mid] > nums[start] || nums[mid] > nums[end]) {
if (target < nums[mid] && target >= nums[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
//If we get here, that means nums[start] == nums[mid] == nums[end], then shifting out
//any of the two sides won't change the result but can help remove duplicate from
//consideration, here we just use end-- but left++ works too
} else {
end--;
}
}

return false;
}
``````
##### Search in Rotated Sorted Array II LeetCode Solution Review:

In our experience, we suggest you solve this Search in Rotated Sorted Array II LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Search in Rotated Sorted Array II LeetCode Solution

Find on Leetcode

##### Conclusion:

I hope this Search in Rotated Sorted Array II LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions