Search in Rotated Sorted Array II

medium

Search a target in a rotated sorted array that may include duplicates

Search in Rotated Sorted Array II

Key Insight

Use normal rotated-array logic, but shrink both ends when duplicates block ordering.

Step 1Setup
Rotated with duplicates
L
R
2
0
5
1
6
2
0
3
0
4
1
5
2
6
Search space: [0..6]

Find target in [2, 5, 6, 0, 0, 1, 2].

1 / 3

Learn the Pattern

Binary SearchEliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
Practice the Code

Step-by-Step Walkthrough: Search in Rotated Sorted Array II

Use normal rotated-array logic, but shrink both ends when duplicates block ordering.

  1. Setup

    Find target in [2, 5, 6, 0, 0, 1, 2].

  2. Mid=3, Value=0

    mid is not target. Boundaries and mid differ, so decide sorted half as normal.

  3. Target Found

    arr[3] == target, so return true.