Search in Rotated Sorted Array II

Medium
812.

Search in Rotated Sorted Array II

Search in Rotated Sorted Array II is a medium coding problem on arrays and binary search, asked in Amazon, Google and Flipkart interviews.

nums was sorted in non-decreasing order, then rotated at some pivot. Duplicates are allowed.

Return whether target is present.

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

Example 3

Input
nums = [1,0,1,1,1], target = 0
Output
true
Explanation
The duplicated 1s hide which half is sorted.

Constraints

  • 1 <= nums.length <= 5000
  • -10000 <= nums[i], target <= 10000
  • nums is a rotation of a non-decreasing array.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Search in Rotated Sorted Array II — Problem & Solution

Search in Rotated Sorted Array II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Search in Rotated Sorted Array II is a medium coding problem on arrays and binary search, asked in Amazon, Google and Flipkart interviews.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google, Flipkart
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums was sorted in non-decreasing order, then rotated at some pivot. Duplicates are allowed.

Return whether target is present.

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

Example 3

Input: nums = [1,0,1,1,1], target = 0
Output: true
Explanation: The duplicated 1s hide which half is sorted.

Constraints

  • 1 <= nums.length <= 5000
  • -10000 <= nums[i], target <= 10000
  • nums is a rotation of a non-decreasing array.

Hints for Search in Rotated Sorted Array II

  1. Hint 1

    In a rotated array, at least one of the two halves around the midpoint is properly sorted.

  2. Hint 2

    Decide which half is sorted, then check whether target falls inside its range.

  3. Hint 3

    Duplicates can make nums[lo] == nums[mid] == nums[hi], which tells you nothing — shrink both ends by one.

How to solve Search in Rotated Sorted Array II

The rotation leaves at least one half sorted, which is enough to decide where target can be. Duplicates break the test for which half is sorted, and the only safe recovery is to narrow both ends by one — which is why the worst case is linear.

Approach

  1. If nums[mid] is the target, answer true.
  2. If nums[lo], nums[mid] and nums[hi] are all equal, advance lo and retreat hi and continue.
  3. If nums[lo] <= nums[mid], the left half is sorted: search it when nums[lo] <= target < nums[mid], else go right.
  4. Otherwise the right half is sorted: search it when nums[mid] < target <= nums[hi], else go left.

Why it works

With nums[lo] <= nums[mid] the left half contains no pivot, so it is genuinely sorted and a range test settles whether target can be there. When all three sampled values are equal, neither half can be ruled out — an adversarial input like [1,1,1,0,1] forces the degenerate step — so the algorithm gives up one element from each side, which is correct but makes the worst case O(n).

Complexity

  • Time — O(log n) average, O(n) worst case with many duplicates
  • Space — O(1)

Pitfalls

  • Omitting the all-equal check makes the 'which half is sorted' test wrong and loses valid targets.
  • Using < instead of <= in nums[lo] <= nums[mid] mishandles a two-element window.
  • The range tests must be half-open on the side that holds nums[mid], or the midpoint is re-examined.

Reference solution

Python

from typing import List

def search(nums: List[int], target: int) -> bool:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return True
        if nums[lo] == nums[mid] == nums[hi]:
            lo += 1
            hi -= 1
            continue
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return False

Java

public static boolean search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] == target) return true;
        if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
            lo++;
            hi--;
            continue;
        }
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
        }
    }
    return false;
}

C++

bool search(vector<int>& nums, int target) {
    int lo = 0, hi = (int) nums.size() - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] == target) return true;
        if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
            lo++;
            hi--;
            continue;
        }
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
        }
    }
    return false;
}

JavaScript

var search = function(nums, target) {
    var lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        var mid = (lo + hi) >> 1;
        if (nums[mid] === target) return true;
        if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) { lo++; hi--; continue; }
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search