Search in Rotated Sorted Array II

MEDIUM

Description

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
-10⁴ <= nums[i] <= 10⁴
nums is guaranteed to be rotated at some pivot.
-10⁴ <= target <= 10⁴

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Approaches

Checkout 2 different approaches to solve Search in Rotated Sorted Array II. Click on different approaches to view the approach and algorithm in detail.

Linear Search

The most straightforward approach is to iterate through each element of the array and check if it matches the target value. This method does not leverage the partially sorted nature of the array.

Algorithm

1. Start a loop that iterates from the first element (index = 0) to the last element (index = nums.length - 1).
1. In each iteration, get the current element nums[i].
1. Compare the current element with the target.
1. If nums[i] == target, the target is found. Return true.
1. If the loop finishes without finding any match, return false.

This brute-force method involves a simple loop that traverses the array from the first element to the last. In each iteration, it compares the current element with the target. If a match is found, the function immediately returns true. If the loop completes without finding the target, it means the target is not in the array, and the function returns false.

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

Complexity Analysis

Time Complexity: O(N)Space Complexity: O(1)

Pros and Cons

Pros:

Very simple to understand and implement.
Guaranteed to work correctly for any input array, regardless of its properties.

Cons:

Highly inefficient, with a time complexity linear to the size of the array.
Fails to utilize the special property of the array (rotated sorted), missing an opportunity for optimization.

Code Solutions

Checking out 4 solutions in different languages for Search in Rotated Sorted Array II. Click on different languages to view the code.

class Solution {
public
  boolean search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] > nums[r]) {
        if (nums[l] <= target && target <= nums[mid]) {
          r = mid;
        } else {
          l = mid + 1;
        }
      } else if (nums[mid] < nums[r]) {
        if (nums[mid] < target && target <= nums[r]) {
          l = mid + 1;
        } else {
          r = mid;
        }
      } else {
        --r;
      }
    }
    return nums[l] == target;
  }
}

Video Solution

Watch the video walkthrough for Search in Rotated Sorted Array II

Algorithms:

Binary Search

Data Structures:

Array

Companies:

Adobe |Amazon |Apple |Bloomberg |