# Leetcode Search in Rotated Sorted Array II problem solution

Apr 25, 2023

In the Leetcode Search in Rotated Sorted Array II problem 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[0], nums[1], …, nums[k-1]. 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

## Solution in C Progamming

``````bool search(int* nums, int numsSize, int target){
int left = 0, right = numsSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] > nums[left]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (nums[mid] < nums[left]) {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
left++;
}
}
return false;
}

int solution(int argc, char *argv[]) {
int nums[] = {2,5,6,0,0,1,2};
int target = 0;
printf("%d\n", search(nums, sizeof(nums)/sizeof(int), target));
return 0;
}``````

## Solution in C++ Programming

``````class Solution {
public:
bool search(vector<int>& nums, int target) {

int n=nums.size();
if(n==0) return false;
int low=0,high=n-1;

if(nums[n-1]>nums[0])  // this is just an extra condition to check if the array has been rotated or not
{
int idx=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
if(idx==n) return false;
if(nums[idx]!=target) return false;
return true;
}

while(low<=high)
{
int mid=low+(high-low)/2;

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

else if(nums[mid]>nums[high])
{
if(nums[mid]>target)
{
if(nums[low]<=target) high=mid-1;
else low=mid+1;
}
else
{
low=mid+1;
}
}

else if(nums[mid]<nums[high])
{
if(nums[mid]>target) high=mid-1;
else
{
if(nums[high]>=target) low=mid+1;
else high=mid-1;
}
}

else high--;
}

return false;
}
};``````

## Solution in Java Programming

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

## Solution in Python Programming

``````class Solution:
def search(self, nums, target):

def binSearch(left, right):

if left > right:
return False

mid = (left + right) // 2
if nums[mid] == target:
return True
elif nums[left] < nums[mid] and (target < nums[left] or target > nums[mid]):
return binSearch(mid+1, right)
elif nums[mid] < nums[right] and (target < nums[mid] or target > nums[right]):
return binSearch(left, mid-1)
else:
return binSearch(left, mid-1) or binSearch(mid+1, right)

return binSearch(0, len(nums)-1)``````

## Solution in C# Programming

``````public class Solution {
public bool Search(int[] nums, int target) {
int len = nums.Length;
int lo = 0;
int hi = len - 1;
while(lo + 1 <= hi && nums[lo + 1] == nums[lo]) lo++;
while(hi - 1 >= lo && nums[hi - 1] == nums[hi]) hi--;
while(lo < hi)
{
int mid = (lo + hi) / 2;
if(nums[mid] == target || nums[lo] == target || nums[hi] == target)
{
return true;
}else if(nums[mid] > nums[lo])
{
if(target > nums[lo] && target < nums[mid])
{
hi = mid - 1;
while(hi - 1 >=0 && nums[hi - 1] == nums[hi]) hi--;
}else
{
lo = mid + 1;
while(lo + 1 < len && nums[lo + 1] == nums[lo]) lo++;
}
}else
{
if(target > nums[mid] && target < nums[hi])
{
lo = mid + 1;
while(lo + 1 < len && nums[lo + 1] == nums[lo]) lo++;
}else
{
hi = mid - 1;
while(hi - 1 >=0 && nums[hi - 1] == nums[hi]) hi--;
}
}
}

return target == nums[lo];
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.