Get started

Search in Rotated Sorted Array II — Medium Problem & Solution

nums was sorted in non-decreasing order, then rotated at some pivot. Duplicates are allowed. Return whether target is present.

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue