Skip to main content
Talentd

Search in Rotated Sorted Array II - Solution & Explanation

MediumArrayBinary Search23 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

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

 

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

 

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?

Approach Overview

Problem Overview: You are given a rotated sorted array that may contain duplicates. The task is to determine whether a target value exists in the array. Unlike the classic rotated array problem, duplicates make it harder to determine which side of the array is sorted, so the search logic needs extra handling.

Approach 1: Modified Binary Search (Average O(log n), Worst O(n) time, O(1) space)

This approach adapts binary search to handle rotation and duplicates. Start with two pointers left and right, compute mid, and check if nums[mid] equals the target. Normally, one half of the rotated array is sorted, which allows you to discard half the search space. The complication appears when nums[left] == nums[mid] == nums[right]; duplicates prevent you from identifying the sorted side. In that case, shrink the window by incrementing left and decrementing right.

If the left half is sorted (nums[left] <= nums[mid]), check whether the target lies between nums[left] and nums[mid]. If it does, move right = mid - 1; otherwise search the other half. If the right half is sorted, apply the same logic symmetrically. This method still behaves like classic rotated-array search in most cases, giving O(log n) performance. However, arrays filled with duplicates can force repeated shrinking of the window, degrading to O(n).

The algorithm uses only index comparisons and constant extra memory, making it efficient and suitable for large arrays. Since the problem revolves around rotated ordering and conditional partitioning, it heavily relies on array traversal combined with decision logic typical in binary search problems.

Approach 2: Linear Search (Fallback) (O(n) time, O(1) space)

The simplest solution iterates through the entire array and checks whether any element equals the target. Use a single loop from index 0 to n-1 and return true when a match is found. If the loop completes without finding the target, return false. This approach ignores the rotated sorted structure completely.

Linear search works reliably regardless of duplicates, rotations, or array ordering. It also becomes the theoretical worst-case behavior of the modified binary search when duplicates prevent meaningful partitioning. While not optimal for large inputs, it is trivial to implement and useful as a correctness baseline or fallback during debugging.

Recommended for interviews: Interviewers expect the modified binary search solution. It shows you understand how rotation affects ordering and how duplicates complicate the decision about which half is sorted. Mentioning the linear scan demonstrates awareness of the brute-force baseline, but implementing the binary search variation shows stronger algorithmic reasoning.

Approach 1: Approach 1: Modified Binary Search

This approach uses a modified binary search to handle the rotated sorted array with duplicates. Normally, in a binary search, you would compare the middle element with the target and adjust your search range accordingly. However, because this array is rotated, the sorted order is disrupted, and duplicates can complicate matters.

The key steps are:

  • Ignore duplicate elements by adjusting the left and right pointers when nums[left] == nums[mid] == nums[right].
  • Determine the sorted half of the array and decide the search direction.

The time complexity is generally O(log N), but in the worst case with duplicates, it can degrade to O(N).

This Python implementation of the modified binary search accounts for duplicates by checking for duplicate middle elements. If they exist, the algorithm adjusts the search boundaries while maintaining the sorted distinction in either half of the array.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

The time complexity is O(log N) in the average case, but O(N) in the worst case due to duplicates. The space complexity is O(1) since no extra storage is needed.

Try this approach in the editor →

Approach 2: Approach 2: Linear Search (Fallback)

In cases of heavy element duplication, when the above methods become inefficient, a linear search ensures completion of the task. Though not ideal for large-sized arrays, this method provides a simple, guaranteed solution without involving complicated logic.

The complexity for linear search is both time and space O(N).

In this simplistic Python solution, we loop through the entire array, checking each element for equality with the target, making it a reliable brute-force method.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Both time and space complexities are O(N), since we traverse the entire array.

Try this approach in the editor →

Approach 3: Binary Search

We define the left boundary of the binary search as l = 0 and the right boundary as r = n - 1, where n is the length of the array.

Each time during the binary search, we get the current midpoint mid = (l + r) / 2.

  • If nums[mid] > nums[r], it means [l, mid] is ordered. If nums[l] \le target \le nums[mid], it means target is in [l, mid]. Otherwise, target is in [mid + 1, r].
  • If nums[mid] < nums[r], it means [mid + 1, r] is ordered. If nums[mid] < target \le nums[r], it means target is in [mid + 1, r]. Otherwise, target is in [l, mid].
  • If nums[mid] = nums[r], it means the elements nums[mid] and nums[r] are equal. In this case, we cannot determine which interval target is in, so we can only decrease r by 1.

After the binary search, if nums[l] = target, it means the target value target exists in the array. Otherwise, it does not exist.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Modified Binary Search

The time complexity is O(log N) in the average case, but O(N) in the worst case due to duplicates. The space complexity is O(1) since no extra storage is needed.

Approach 2: Linear Search (Fallback)

Both time and space complexities are O(N), since we traverse the entire array.

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Modified Binary SearchO(log n) average, O(n) worstO(1)Best general solution for rotated sorted arrays with duplicates
Linear Search (Fallback)O(n)O(1)Small arrays, quick baseline implementation, or debugging

Video Solution

BS-5. Search Element in Rotated Sorted Array II • take U forward • 443,408 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Search in Rotated Sorted Array II easy or hard?
The problem is generally classified as medium difficulty. The base idea of binary search is straightforward, but handling duplicates while still determining the sorted half of a rotated array adds subtle edge cases.
Search in Rotated Sorted Array II Python/Java solution
Most implementations follow the same modified binary search logic across languages. Maintain left and right pointers, compute mid, compare with the target, and adjust boundaries depending on which side is sorted. Python, Java, C++, C#, and JavaScript solutions differ mainly in syntax but use identical algorithmic steps.
How to solve Search in Rotated Sorted Array II in O(n)?
An O(n) solution simply performs a linear scan through the array. Iterate from index 0 to n-1 and check whether any element equals the target value. This approach ignores rotation and duplicates but guarantees correctness with constant space.
What is the best approach for Search in Rotated Sorted Array II?
The best approach uses modified binary search. By checking which half of the rotated array is sorted and narrowing the search space accordingly, you can usually achieve O(log n) time. Duplicates may obscure the sorted side, so the algorithm sometimes shrinks both boundaries, leading to a worst-case O(n).
Is Search in Rotated Sorted Array II asked at Google/Amazon/Meta?
Rotated array search problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants without duplicates are more common, but this version tests how you handle ambiguous ordering caused by duplicate elements during binary search.
What data structure is used in Search in Rotated Sorted Array II?
The problem uses a simple array as the underlying data structure. The main technique applied on top of it is binary search logic with pointer manipulation to determine which half of the rotated array remains sorted.
What is the time complexity of Search in Rotated Sorted Array II?
Modified binary search runs in O(log n) on average because it discards half of the search space each step. However, when many duplicate values appear (for example nums[left] == nums[mid] == nums[right]), the algorithm may only shrink the range by one element at a time, resulting in O(n) worst-case complexity.

Ready to solve this problem?

Practice Search in Rotated Sorted Array II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Search in Rotated Sorted Array