Here, We see Search in Rotated Sorted Array II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Search in Rotated Sorted Array II LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Search in Rotated Sorted Array II LeetCode Solution
Table of Contents
Problem Statement
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
Search in Rotated Sorted Array II Leetcode Solution C++
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
int m = l + (r - l) / 2;
if (nums[m] == target) {
return true;
}
if (nums[m] > target) {
if (nums[l] > nums[m] || nums[l] <= target) {
r = m - 1;
} else {
l = m + 1;
}
} else {
if (nums[l] <= nums[m] || nums[l] > target) {
l = m + 1;
} else {
r = m - 1;
}
}
}
return false;
}
};
Code language: PHP (php)
Search in Rotated Sorted Array II Leetcode Solution Java
class Solution {
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 (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;
}
}
Code language: PHP (php)
Search in Rotated Sorted Array II Leetcode Solution JavaScript
var search = function(nums, target) {
function findPivot(low, high) {
if(high - low === 1 && nums[high] < nums[low]) return high;
if(high - low <= 1) return 0;
const mid = Math.floor((low + high) / 2);
if(nums[mid] > nums[high]) return findPivot(mid, high);
if(nums[mid] < nums[low]) return findPivot(low, mid);
return Math.max(findPivot(low, mid), findPivot(mid, high));
}
function binarySearch(start, end) {
while(start <= end) {
const mid = Math.floor((start + end) / 2);
if(nums[mid] === target) return true;
if(nums[mid] > target) end = mid - 1;
else start = mid + 1;
}
return false;
}
const minIdx = findPivot(0, nums.length-1)
return binarySearch(0, minIdx-1) || binarySearch(minIdx, nums.length-1)
};
Code language: JavaScript (javascript)
Search in Rotated Sorted Array II Leetcode Solution Python
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
left,right = 0,len(nums)-1
while left <= right:
mid = (left+right) // 2
if nums[mid] == target:
return True
if nums[left] <= nums[mid]:
if nums[left] == nums[mid] and mid != left:
left+=1
continue
if nums[left] <= target< nums[mid]:
right = mid-1
else: left = mid+1
elif nums[left] > nums[mid]:
if nums[mid] < target <= nums[right]:
left = mid+1
else: right = mid-1
return False