Coding Interview PatternsSearch in Rotated Sorted Array II
MediumModified Binary Search

Search in Rotated Sorted Array II

Explanation & Solution

Practice Problem

Description

Given an integer array nums sorted in ascending order which may contain duplicates, and is possibly rotated at an unknown pivot, return true if target is in nums, or false otherwise.

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

Input:nums = [2, 5, 6, 0, 0, 1, 2], target = 0
0
2
1
5
2
6
3
0
4
0
5
1
6
2

Output: true

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted and rotated between 1 and n times
  • -10^4 <= target <= 10^4

Approach

Modified Binary Search pattern

1. Initialize Pointers

  • Set left = 0 and right = nums.length - 1.

2. Handle the Duplicate Edge Case

  • If nums[left] === nums[mid] === nums[right], we cannot determine which half is sorted.
  • Shrink both ends: left++, right--. This is the key difference from Search in Rotated Sorted Array I.

3. Standard Rotated Binary Search

  • If nums[left] <= nums[mid], the left half is sorted → check if target is in [nums[left], nums[mid]).
  • Otherwise, the right half is sorted → check if target is in (nums[mid], nums[right]].

4. Return Result

  • Return true if found, false if the loop ends.

🧠 Key Insight

  • Duplicates make it impossible to determine the sorted half in some cases, requiring a linear shrink step.
Time
O(log n) average, O(n) worst case when all elements are duplicates.
Space
O(1).

Visualization

Input:
[2, 5, 6, 0, 0, 1, 2], target = 0
20516203041526
—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone
4 steps

Solution Code

Previous
Search in Rotated Sorted Array
Next
Find Minimum in Rotated Sorted Array