Skip to content

0081. Search in Rotated Sorted Array II

Table of Contents

  1. Problem
  2. Problem Breakdown
  3. Approach 1: Linear Scan
  4. Approach 2: Modified Binary Search
  5. Complexity Comparison
  6. Edge Cases
  7. Common Mistakes
  8. Related Problems
  9. Visual Animation

Problem
Leetcode 81. Search in Rotated Sorted Array II
Difficulty 🟡 Medium
Tags Array, Binary Search

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.

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not.

You must decrease the overall operation steps as much as possible.

Examples

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

Problem Breakdown

1. What is being asked?

Given a rotated sorted array that may contain duplicates, decide whether target exists.

2. Key Difference from Problem 33

Duplicates can prevent us from determining which half is sorted: if nums[lo] == nums[mid] == nums[hi], we cannot tell. Resolve by shrinking lo++, hi-- (worst case O(n)).

Approach 1: Linear Scan

Idea

Walk all n elements. O(n).

Implementation

Python

class Solution:
    def searchLinear(self, nums: List[int], target: int) -> bool:
        return target in nums

Algorithm

  1. lo = 0, hi = n - 1.
  2. While lo <= hi:
  3. mid = (lo + hi) // 2. If nums[mid] == target: return true.
  4. If nums[lo] == nums[mid] == nums[hi]: lo++; hi--.
  5. Else if left half sorted (nums[lo] <= nums[mid]):
    • If nums[lo] <= target < nums[mid]: hi = mid - 1. Else lo = mid + 1.
  6. Else (right half sorted):
    • If nums[mid] < target <= nums[hi]: lo = mid + 1. Else hi = mid - 1.
  7. Return false.

Complexity

Complexity
Time O(log n) average; O(n) worst (all duplicates)
Space O(1)

Implementation

Go

func search(nums []int, target int) bool {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        if nums[mid] == target {
            return true
        }
        if nums[lo] == nums[mid] && nums[mid] == nums[hi] {
            lo++
            hi--
        } else 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
}

Java

class Solution {
    public 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--;
            } else 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;
    }
}

Python

class Solution:
    def search(self, 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
            elif 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

Complexity Comparison

# Approach Time Space
1 Linear O(n) O(1)
2 Binary Search O(log n) avg, O(n) worst O(1)

Edge Cases

# Case Reason
1 All duplicates [1,1,1,1], target = 1 True
2 All duplicates, target absent False (degrades to O(n))
3 Not rotated Standard binary search
4 Pivot at start Whole array is sorted
5 Single element match True
6 Single element miss False

Common Mistakes

Mistake 1: Forgetting the duplicate-shrinking branch

# WRONG — without nums[lo] == nums[mid] == nums[hi] handling, breaks for [1,1,1,2,1]

Mistake 2: Off-by-one in target ranges

if nums[lo] <= target < nums[mid]: hi = mid - 1   # left side, half-open
if nums[mid] < target <= nums[hi]: lo = mid + 1   # right side, half-open
# Problem Difficulty Similarity
1 33. Search in Rotated Sorted Array 🟡 Medium Same without duplicates
2 153. Find Minimum in Rotated Sorted Array 🟡 Medium Find pivot

Visual Animation

Interactive animation: animation.html