DSA-062 · FOCUSED PRACTICE

Search in Rotated Sorted Array

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 11469 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the index of target in a rotation of a strictly increasing int array, or −1 if absent. The rotation may be zero. Preserve the array and search logarithmically.

nums is nonnull, has at most 100,000 distinct ints, and is a cyclic rotation of one strictly increasing sequence. Distinctness and rotation structure are unchecked preconditions; arbitrary or duplicate-valued arrays are outside the API.
Return the unique matching index or −1. An empty array returns −1; an unrotated array and a one-element array are valid rotations.
Both implementations leave every value unchanged. null throws NullPointerException. The optimized interval is closed [left,right], initially [0,n−1].

Examples

Input: [4,5,6,7,0,1,2], target=0
Output: 4
The left side through index 3 is sorted but excludes zero, so search the right side.
Input: [3,1], target=2
Output: −1
Distinctness permits deciding the sorted singleton/half and shrinking to exhaustion.
Input: [MIN,0,MAX], target=MIN
Output: 0
No rotation and extreme values use the same comparisons.

Before you start

Closed binary-search intervals
Rotation of a strictly increasing sequence

Recognize the structure

A rotated strictly increasing array has at most one descending break. Splitting at a midpoint leaves at least one sorted half, whose endpoint values tell whether it can contain the target. Global array monotonicity is absent, so ordinary target binary search is not directly valid.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 124/20,000 characters

Self-review

I explain why one half must be sorted.My range tests include outer boundaries and exclude the already-tested midpoint.I do not claim the distinct-value proof handles duplicate ambiguity.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

A single rotation introduces only one descending break.

Hint 2

At least one of [left,mid] and [mid,right] is sorted.

Hint 3

Test whether target lies inside the sorted half’s value range, then keep only the possible half.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Scan the rotated sequence

Inspect every position and return equality, otherwise −1. For [4,5,6,7,0,1,2], target=0, the linear scan finds index 4 after five checks. This O(n)-time, O(1)-space baseline ignores structure; the optimized method uses the single-break promise to discard a half.

Improve the baseline

Check the midpoint first

If nums[mid]==target, return it. For the remaining branches mid is proven not to be the answer, so closed-interval updates may exclude it.

Identify a sorted side

If nums[left]<=nums[mid], the left half is sorted, including a singleton half. Keep it only when nums[left]<=target<nums[mid]; otherwise keep the right side.

Handle the opposite side symmetrically

If the left half is not sorted, the right half must be sorted. Keep it when nums[mid]<target<=nums[right], otherwise keep the left. Use mid±1 and stop at left>right.

Why it is correct

Candidate and structure invariant

Any matching index stays in [left,right]. An active contiguous segment of a one-break array has at most one break, so at least one half about mid is sorted.

Safe elimination

In a sorted half with distinct endpoints, the target belongs there exactly when its value falls between those endpoints with midpoint equality excluded. If it does not, that half cannot contain a match; uniqueness and the rotation promise justify keeping the opposite half.

Progress

After failed midpoint equality, either left becomes mid+1 or right becomes mid−1. The candidate interval strictly shrinks by a constant factor and eventually returns a valid index or exhausts, with no mutation.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    public static int search(int[] nums, int target) {
        Objects.requireNonNull(nums, "nums");
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }
    public static int baseline(int[] nums, int target) {
        Objects.requireNonNull(nums, "nums");
        for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
        return -1;
    }
}

Read the meaningful blocks

Closed bounds

right=n−1 and left<=right include the last candidate. Empty input starts right=−1 and skips the loop.

Inclusive outer endpoints

Use <= at the original left/right endpoints but strict inequality at mid because equality was already checked.

Distinctness matters

nums[left]<=nums[mid] identifies the sorted half under the unique-value contract. Equal repeated boundary values can hide the pivot and require a different algorithm.

Complexity

Optimized search takes O(log(n+1)) time and O(1) workspace. The input promises are not validated by a full scan.

The baseline takes O(n) time. If duplicates are permitted, ambiguous equal boundaries may require one-at-a-time shrinking and O(n) worst-case work.

Exact-state walkthroughs

Reveal normal and boundary traces

Target lies beyond the descending break

Input: {"nums":[4,5,6,7,0,1,2],"target":0} · Returned index: 4

Step 1 of 5: Initialize a closed candidate interval.

The unique target, if present, remains in the active interval.

Rotated lookup — sorted-side selection

Candidate element interval: [0, 6]. Phase: search. Target: 0.

index 04retained element
index 15retained element
index 26retained element
index 37retained element
index 40retained element
index 51retained element
index 62retained element

Highlight marks the last probed element, which may have just been discarded. Only indices inside the retained interval remain candidates unless a match has already been found.

State after this step
Variable	Value
values	`[4,5,6,7,0,1,2]`
target	`0`
left	`0`
right	`6`
bounds	`"closed"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int search(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int left = 0, right = nums.length - 1;
 7         while (left <= right) {
 8             int mid = left + (right - left) / 2;
 9             if (nums[mid] == target) return mid;
10             if (nums[left] <= nums[mid]) {
11                 if (nums[left] <= target && target < nums[mid]) right = mid - 1;
12                 else left = mid + 1;
13             } else {
14                 if (nums[mid] < target && target <= nums[right]) left = mid + 1;
15                 else right = mid - 1;
16             }
17         }
18         return -1;
19     }
20     public static int baseline(int[] nums, int target) {
21         Objects.requireNonNull(nums, "nums");
22         for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
23         return -1;
24     }
25 }
26

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize a closed candidate interval.
The unique target, if present, remains in the active interval.
values
[4,5,6,7,0,1,2]
target
0
left
0
right
6
bounds
"closed"
phase
"search"
Use the sorted left half to retain the possible target side.
Outer endpoints are inclusive; midpoint equality was already rejected, so mid itself is excluded.
values
[4,5,6,7,0,1,2]
target
0
left
4
right
6
bounds
"closed"
phase
"search"
before
[0,6]
mid
3
probeValue
7
found
false
sortedSide
"left"
targetInsideSortedHalf
false
Use the sorted left half to retain the possible target side.
Outer endpoints are inclusive; midpoint equality was already rejected, so mid itself is excluded.
values
[4,5,6,7,0,1,2]
target
0
left
4
right
4
bounds
"closed"
phase
"search"
before
[4,6]
mid
5
probeValue
1
found
false
sortedSide
"left"
targetInsideSortedHalf
true
Return the unique equality witness.
This original index is the target; no mutation or pivot reconstruction is required.
values
[4,5,6,7,0,1,2]
target
0
left
4
right
4
bounds
"closed"
phase
"search"
before
[4,4]
mid
4
probeValue
0
found
true
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
4

Absent in a two-element rotation

Input: {"nums":[3,1],"target":2} · Returned index: -1

Step 1 of 4: Initialize a closed candidate interval.

The unique target, if present, remains in the active interval.

Rotated lookup — sorted-side selection

Candidate element interval: [0, 1]. Phase: search. Target: 2.

index 03retained element
index 11retained element

Highlight marks the last probed element, which may have just been discarded. Only indices inside the retained interval remain candidates unless a match has already been found.

State after this step
Variable	Value
values	`[3,1]`
target	`2`
left	`0`
right	`1`
bounds	`"closed"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int search(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int left = 0, right = nums.length - 1;
 7         while (left <= right) {
 8             int mid = left + (right - left) / 2;
 9             if (nums[mid] == target) return mid;
10             if (nums[left] <= nums[mid]) {
11                 if (nums[left] <= target && target < nums[mid]) right = mid - 1;
12                 else left = mid + 1;
13             } else {
14                 if (nums[mid] < target && target <= nums[right]) left = mid + 1;
15                 else right = mid - 1;
16             }
17         }
18         return -1;
19     }
20     public static int baseline(int[] nums, int target) {
21         Objects.requireNonNull(nums, "nums");
22         for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
23         return -1;
24     }
25 }
26

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize a closed candidate interval.
The unique target, if present, remains in the active interval.
values
[3,1]
target
2
left
0
right
1
bounds
"closed"
phase
"search"
Use the sorted left half to retain the possible target side.
Outer endpoints are inclusive; midpoint equality was already rejected, so mid itself is excluded.
values
[3,1]
target
2
left
1
right
1
bounds
"closed"
phase
"search"
before
[0,1]
mid
0
probeValue
3
found
false
sortedSide
"left"
targetInsideSortedHalf
false
Use the sorted left half to retain the possible target side.
Outer endpoints are inclusive; midpoint equality was already rejected, so mid itself is excluded.
values
[3,1]
target
2
left
2
right
1
bounds
"closed"
phase
"search"
before
[1,1]
mid
1
probeValue
1
found
false
sortedSide
"left"
targetInsideSortedHalf
false
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
-1

Empty rotated search

Input: {"nums":[],"target":5} · Returned index: -1

Step 1 of 2: Initialize a closed candidate interval.

The unique target, if present, remains in the active interval.

Rotated lookup — sorted-side selection

Candidate element interval: [0, -1]. Phase: search. Target: 5.

Empty array — no probeable elements.

Highlight marks the last probed element, which may have just been discarded. Only indices inside the retained interval remain candidates unless a match has already been found.

State after this step
Variable	Value
values	`[]`
target	`5`
left	`0`
right	`-1`
bounds	`"closed"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int search(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int left = 0, right = nums.length - 1;
 7         while (left <= right) {
 8             int mid = left + (right - left) / 2;
 9             if (nums[mid] == target) return mid;
10             if (nums[left] <= nums[mid]) {
11                 if (nums[left] <= target && target < nums[mid]) right = mid - 1;
12                 else left = mid + 1;
13             } else {
14                 if (nums[mid] < target && target <= nums[right]) left = mid + 1;
15                 else right = mid - 1;
16             }
17         }
18         return -1;
19     }
20     public static int baseline(int[] nums, int target) {
21         Objects.requireNonNull(nums, "nums");
22         for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
23         return -1;
24     }
25 }
26

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize a closed candidate interval.
The unique target, if present, remains in the active interval.
values
[]
target
5
left
0
right
-1
bounds
"closed"
phase
"search"
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
-1

Test the contract

Input: []
Output: −1
Empty closed interval.
Input: [1], target=1
Output: 0
Singleton sorted half.
Input: [4,5,6,7,0,1,2], target=0
Output: 4
Pivot-crossing case.
Input: [3,1], target=2
Output: −1
Absent between two rotated values.
Input: Every rotation of every small distinct subset
Output: Correct unique index or −1
All pivot placements and endpoints.

Common mistakes and counterexamples

Apply ordinary sorted search to the whole array

Counterexample: [4,5,6,7,0,1,2], target=0 cannot be ordered against mid without locating the sorted side.

Identify which half is sorted before comparing its range.

Exclude the outer endpoint from the membership test

Counterexample: Using nums[left]<target loses a target exactly at left.

Use nums[left]<=target or target<=nums[right] as appropriate.

Reuse the distinct proof with duplicates

Counterexample: [1,0,1,1,1], target=0 has equal left/mid/right values that conceal the break.

State the distinct contract; the duplicate variant needs ambiguity handling and weaker complexity.

Retain mid after failed equality

Counterexample: A two-element active interval can fail to shrink.

Because mid is not a match, discard it using mid+1 or mid−1.

Follow-ups

Allow duplicates.

When left, mid, and right values cannot distinguish a sorted side, shrink ambiguous boundaries carefully after equality checks. Explain why the worst case degrades to linear time.

Find the pivot, then search.

Find the minimum index with DSA-063’s reasoning, select one sorted segment by endpoint values, and binary-search it. Two logarithmic stages remain logarithmic but need explicit index ranges.

Return the rotation count.

Define rotation direction first. The minimum index is the right-rotation count modulo n for the usual right-rotation convention, but a left-rotation amount has the complementary relationship.

Related foundations

Binary search: candidate intervals and monotone feasibility

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.