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.

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
  1. 1 <= nums.length <= 5000
  2. -104 <= nums[i] <= 104
  3. nums is guaranteed to be rotated at some pivot.
  4. -104 <= target <= 104

Solutions

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
  1. We’ll look through each element in the array to see if it matches k. If we find a match, we’ll return True.
  2. If there’s no match, we’ll return False.

 

Code
				
					class Solution {
public:
    bool search(vector<int>& 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.

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:

  1. Initialization: Begin by setting up two pointers, low at the start of the list and high at the end of the list.

  2. Binary Search: Employ a modified binary search to find the target within this rotated list.

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

  4. Middle Element Calculation: Calculate the mid index by averaging the low and high indices.

  5. Check Middle Element: Examine if the target matches the number at the mid index. If it does, return True as the target is found.

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

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

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

  9. 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<int>& 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
  1. Initialization: Set two pointers, low at the start of the array and high at the end of the array to define the search range.

  2. Binary Search: Use a modified binary search approach to look for the target within the rotated sorted array.

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

  4. Calculate Middle: Calculate the mid index as the average of the low and high indices to check the middle element.

  5. Check Middle Element: If the element at mid matches the target, return true as the target is found.

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

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Welcome to our diverse learning options!

Select the learning format that suits your preferences and schedule.