## Algorithm

Problem Name: 81. Search in Rotated Sorted Array II

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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
bool search(int* nums, int numsSize, int target){
int start, end, mid;
start = 0; end = numsSize - 1;
while (start  < = end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) return true;
if (nums[start] == nums[mid]) {
start ++;
} else if (nums[start]  <  nums[mid]) { // first half are sorted
if (target  >  nums[mid] || target < nums[start]) {
start = mid + 1;
} else {
end = mid - 1;
}
} else { // second half are sorted
if (target  <  nums[mid] || target > nums[end]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
}
return false;
}
``````
Copy The Code &

Input

cmd
nums = [2,5,6,0,0,1,2], target = 0

Output

cmd
true

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (start  < = end) {
int mid = (start + end) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid]  <  nums[end] || nums[mid] < nums[start]) {
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
} else if (nums[mid] > nums[start] || nums[mid] > nums[end]) {
if (target  <  nums[mid] && target >= nums[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
end--;
}
}
return false;
}
}
``````
Copy The Code &

Input

cmd
nums = [2,5,6,0,0,1,2], target = 0

Output

cmd
true

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
class Solution:
def search(self, nums, target):
l, r, n = 0, len(nums) - 1, len(nums)
while l <= r:
while l + 1 < n and nums[l + 1] == nums[l]:
l += 1
while r > 0 and nums[r] == nums[r - 1]:
r -= 1
mid = (l + r) // 2
if nums[mid] == target:
return True
elif sum((target < nums[l], nums[l] <= nums[mid], nums[mid] < target)) == 2:
l = mid + 1
else:
r = mid - 1
return False
``````
Copy The Code &

Input

cmd
nums = [2,5,6,0,0,1,2], target = 3

Output

cmd
false

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def search(self, nums, target):
l, r, n = 0, len(nums) - 1, len(nums)
while l <= r:
while l + 1 < n and nums[l + 1] == nums[l]:
l += 1
while r > 0 and nums[r] == nums[r - 1]:
r -= 1
mid = (l + r) // 2
if nums[mid] == target:
return True
elif sum((target < nums[l], nums[l] <= nums[mid], nums[mid] < target)) == 2:
l = mid + 1
else:
r = mid - 1
return False
``````
Copy The Code &

Input

cmd
nums = [2,5,6,0,0,1,2], target = 3

Output

cmd
false

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _081_SearchInRotatedSortedArray2
{
public bool Search(int[] nums, int target)
{
int lo = 0, hi = nums.Length - 1;
int mid, loValue, hiValue, midValue;

while (lo  < = hi)
{
loValue = nums[lo];
hiValue = nums[hi];
if (loValue  <  hiValue && (target < loValue || target > hiValue))
{
return false;
}

while (lo < hi && nums[lo] == hiValue)
{
lo++;
}
loValue = nums[lo];

mid = lo + (hi - lo) / 2;
midValue = nums[mid];
if (target == midValue) { return true; }

if (loValue  < = midValue)
{
if (loValue <= target && target < midValue)
{
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
else
{
if (target  < = hiValue && midValue < target)
{
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
}

return false;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [2,5,6,0,0,1,2], target = 0

Output

cmd
true