menu

### Search in Rotated Sorted Array II

**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.

##
Examples

**Example 1:**

Input:nums = [2,5,6,0,0,1,2], target = 0Output:true

**Example 2:**

Input:nums = [2,5,6,0,0,1,2], target = 3Output:false

##
Constraints

`1 <= nums.length <= 5000`

`-10`

^{4}<= nums[i] <= 10^{4}`nums`

is guaranteed to be rotated at some pivot.`-10`

^{4}<= target <= 10^{4}

### Solutions

##
Brute Force Approach

##### Approach

One simple way to tackle this is by using the linear search method. With this method, we’ll go through the array to see if the thing we’re looking for is there. If we find it, we’ll say “yes,” otherwise, we’ll say “no.”

##### Algorithm

- We’ll look through each element in the array to see if it matches k. If we find a match, we’ll return True.
- If there’s no match, we’ll return False.

##### Code

` ````
```class Solution {
public:
bool search(vector& nums, int target) {
for (int num : nums) {
if (num == target) {
return true;
}
}
return false;
}
};

` ````
```class Solution:
def search(self, nums: List[int], target: int) -> bool:
for num in nums:
if num == target:
return True
return False

` ````
```class Solution {
public boolean search(int[] nums, int target) {
for (int num : nums) {
if (num == target) {
return true;
}
}
return false;
}
}

##### Time and Space Complexity

Time Complexity: O(N) – because we have to go through enire array.

Space Complexity: O(1) because we are not using any other additional space.

##
Optimised Approach

##### Algorithm

Using Binary Search

##### Intuition

Imagine you have a sorted list of numbers that has been rotated at some pivot point. You’re given a target number, and your task is to figure out if this target exists within this rotated list efficiently.

Here’s how the code achieves this:

**Initialization:**Begin by setting up two pointers,`low`

at the start of the list and`high`

at the end of the list.**Binary Search:**Employ a modified binary search to find the`target`

within this rotated list.**While Loop:**Continue the search until`low`

pointer is less than or equal to the`high`

pointer. This signifies that there’s still a range to search within.**Middle Element Calculation:**Calculate the`mid`

index by averaging the`low`

and`high`

indices.**Check Middle Element:**Examine if the`target`

matches the number at the`mid`

index. If it does, return`True`

as the target is found.**Handle Duplicates:**If the number at`low`

is equal to the number at`mid`

, increment`low`

by 1 and continue. This handles cases where duplicates might be present and disrupt the search.**Check Segments:**Determine if the segment from`low`

to`mid`

is sorted. If it is, check if the`target`

lies within this segment. Adjust`low`

and`high`

pointers accordingly for the next iteration.**Repeat or Conclude:**Based on comparisons, either reduce the search space (adjust pointers) or conclude that the`target`

doesn’t exist in the current segment.**Return False:**If the`target`

is not found after the while loop, return`False`

.

This algorithm takes advantage of the sorted property of segments within the rotated array and adapts the binary search approach to efficiently locate the `target`

element within this modified structure.

##### Short Video Explanation

For a better understanding of the algorithm, please watch the video by clicking on the button below.

##### Code

` ````
```class Solution {
public:
bool search(vector& nums, int target) {
int low = 0;
int high = nums.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[low] == nums[mid]) {
low++;
continue;
}
if (nums[low] <= nums[mid]) {
if (nums[low] <= target && target <= nums[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
if (nums[mid] <= target && target <= nums[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return false;
}
};

` ````
```class Solution:
def search(self, nums: List[int], target: int) -> bool:
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return True
if nums[low] == nums[mid]:
low += 1
continue
if nums[low] <= nums[mid]:
if nums[low] <= target <= nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] <= target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return False

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

##### Explanation

**Initialization:**Set two pointers,`low`

at the start of the array and`high`

at the end of the array to define the search range.**Binary Search:**Use a modified binary search approach to look for the`target`

within the rotated sorted array.**Looping Condition:**Continue the search while the`low`

pointer is less than or equal to the`high`

pointer. This ensures there’s a range to search within.**Calculate Middle:**Calculate the`mid`

index as the average of the`low`

and`high`

indices to check the middle element.**Check Middle Element:**If the element at`mid`

matches the`target`

, return`true`

as the target is found.**Handle Duplicates:**If the element at`low`

is equal to the element at`mid`

, increment`low`

by 1 to skip duplicates and continue the loop.**Check Segments:**Determine if the segment from`low`

to`mid`

is sorted. If it is, check if the`target`

lies within this segment. Adjust`low`

and`high`

pointers accordingly for the next iteration.**Adjust Pointers:**Based on comparisons and sorted segments, either decrease the search space by adjusting pointers or conclude that the`target`

doesn’t exist in the current segment.**Repeat or Conclude:**Continue the loop until the search space is exhausted (`low`

>`high`

) or return`true`

when the`target`

is found. If the loop completes without finding the`target`

, return`false`

.

##### Time and Space Complexity

__Time Complexity:__ In the best and average cases, the time complexity is O(logN), while in the worst case, it’s O(N/2). Here, N represents the size of the provided array.

__Space Complexity:__ O(1) because we have not used in extra space.

WhatsApp

Facebook

Twitter

LinkedIn

Email