Search in Rotated Sorted Array

1. Problem & Core Objective

A sorted array of distinct integers, rotated an unknown number of times. Return the index of target, or -1. Required: O(log n).

nums = [4,5,6,7,0,1,2], target = 0   →  4
nums = [4,5,6,7,0,1,2], target = 3   →  -1
nums = [1], target = 0               →  -1

Constraints: 1 <= n <= 5000 · values in [-10^4, 10^4] · distinct · rotated between 1 and n times

What's actually being tested: in a rotated array, nums[mid] < target no longer tells you which way to go — the array isn't globally sorted. The insight is that one half is always still sorted, and you can decide using that half's range.

2. First-Principles Thought Process

Why plain binary search breaks

In a sorted array, nums[mid] < target means "go right". In [4,5,6,7,0,1,2] searching for 0: mid = 3, nums[3] = 7 > 0, so plain binary search goes left — into [4,5,6], which doesn't contain 0.

The comparison is meaningless because the array isn't globally ordered.

The structural fact that saves it

Pick any mid. The pivot lies in exactly one half — so the other half is entirely within one sorted run, and is therefore properly sorted.

The two-step decision

1. Which half is sorted? Compare nums[lo] against nums[mid].

   • nums[lo] <= nums[mid] → the left half [lo, mid] is sorted.
   • Otherwise the pivot is in the left half, so the right half [mid, hi] is sorted.

2. Is the target inside that sorted half? Because it's sorted, membership is a simple range check on its endpoints.

   • If yes, search there. If no, search the other half.

The unsorted half needs no reasoning at all — you only ever ask about the sorted one.

Why <= in the sortedness test

nums[lo] <= nums[mid] uses <= to cover the two-element case where lo == mid. With strict < that comparison is false, and you'd wrongly conclude the right half is sorted.

Why the range bounds are asymmetric

if (nums[lo] <= target && target < nums[mid])   hi = mid - 1;   // left  half: [lo, mid)
if (nums[mid] < target && target <= nums[hi])   lo = mid + 1;   // right half: (mid, hi]

Each uses the closed end of its own sorted half and excludes nums[mid] — because mid was already tested for equality at the top of the loop. Getting these inclusive/exclusive ends backwards is the second most common bug here.

3. Solution Paths

Approach 1 — Linear scan (brute force)

public int search(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "The array is rotated but still highly structured. What are you ignoring?"

That it's two sorted runs. At any midpoint, one half is guaranteed to be fully sorted — and within a sorted range I can decide membership with two comparisons. That's enough to halve the space each step. The scan treats the input as unordered.

"At n = 5000 would this pass?"

Comfortably. But the problem states O(log n), and the whole point is exploiting the rotation structure, so it's a baseline rather than an answer.

Approach 2 — Find the pivot, then search (two passes)

public int search(int[] nums, int target) {
    int n = nums.length;

    int lo = 0, hi = n - 1;                      // 1. locate the pivot (see question 4)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else                      hi = mid;
    }
    int pivot = lo;

    // 2. binary search the rotated index space, mapping back with modulo
    lo = 0; hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int real = (mid + pivot) % n;            // map to the true position
        if (nums[real] == target) return real;
        if (nums[real] < target) lo = mid + 1;
        else                     hi = mid - 1;
    }
    return -1;
}

How it works. Find the pivot, then treat the array as virtually sorted by offsetting every index by the pivot.

• Time O(log n) — two searches · Space O(1)

Counter-questions on this approach

⭐ "This is also O(log n). Why prefer the single-pass version?"

Two searches, two sets of boundary conditions, plus index arithmetic with a modulo — three places to get something wrong instead of one. It's genuinely the same complexity, so the argument is surface area for bugs, not speed.

That said, it has a real virtue: it reuses the pivot-finding routine from the previous question, so if I'd just written that, this is the lower-risk path. I'd mention both and let the interviewer choose.

"Explain the (mid + pivot) % n mapping."

The rotated array is the sorted array shifted left by pivot. So virtual index 0 corresponds to real index pivot, virtual 1 to pivot + 1, and so on, wrapping with modulo. Searching the virtual space is searching a properly sorted array, which is why plain binary search works on it.

"Does this still work when the array isn't rotated?"

Yes — the pivot search returns 0, so (mid + 0) % n == mid and it degenerates to plain binary search. Worth checking, since that's the input that breaks careless rotation handling.

Approach 3 — One pass, decide by sorted half (optimal)

public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;            // INCLUSIVE bounds

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {                          // LEFT half is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;   // inside it
            else                                          lo = mid + 1;   // not inside it
        } else {                                              // RIGHT half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else                                          hi = mid - 1;
        }
    }
    return -1;
}

Trace — [4,5,6,7,0,1,2], target 0:

Trace — same array, target 3: step 1 sends it right, step 2's sorted half [0..1] excludes 3, so it goes right again into [2,2], fails, and lo passes hi → -1. ✓

• Time O(log n) · Space O(1)

Counter-questions on this approach

⭐ "Why does checking only the sorted half suffice? You never reason about the other one."

Because the two halves partition the array. If the target is in the sorted half's range, it can only be there — the ranges don't overlap, since the array is a rotation of a sorted sequence. If it isn't in that range, it must be in the other half or absent entirely. Either way, one range check decides the direction.

The unsorted half is unsearchable at this step, but at the next step its own midpoint will again have one sorted side. The structure regenerates.

⭐ "Why nums[lo] <= nums[mid] with <= rather than <?"

To cover lo == mid, which happens on a two-element range. With strict < the test is false and you'd take the "right half is sorted" branch, then evaluate nums[mid] < target && target <= nums[hi] — which can send you the wrong way. [3,1] searching for 1 is the minimal case.

"The two range checks have different inclusive ends. Is that deliberate?"

Yes. The left check is nums[lo] <= target && target < nums[mid] — closed at lo, open at mid. The right is nums[mid] < target && target <= nums[hi] — open at mid, closed at hi. Each uses the closed end of its own half and excludes mid, because mid was already tested for equality at the top of the loop. Including mid on either side would be harmless but redundant; getting the outer end wrong loses answers at the array boundaries.

"Does this handle the non-rotated array?"

Yes, with no special case. On [1,2,3,4,5], nums[lo] <= nums[mid] is always true, so it always takes the left-sorted branch — which is exactly plain binary search. Rotation by zero degenerates correctly.

"What if there were duplicates?"

nums[lo] <= nums[mid] becomes uninformative when they're equal — you can't tell which half is sorted. Consider [1,1,1,0,1]. The fix is to advance lo by one and retry, which degrades the worst case to O(n). See §7.

Comparison

4. Why the Optimal Wins

Against the scan: the rotation preserves enough order that one comparison still eliminates half the array — it just takes two comparisons instead of one to work out which half.

Against the two-pass version: identical complexity. The one-pass version has a single loop and a single bound convention; the two-pass version has two searches plus modulo index mapping. It's a bug-surface argument, and I'd say so rather than inventing a performance claim.

O(log n) is the floor, by the same information-theoretic argument as plain binary search.

The transferable idea:

When a structure is only locally ordered, find the part that still carries the full guarantee and make your decision there.

You never reason about the unsorted half — you just note that the target isn't in the sorted one and move on.

5. Java Prerequisites

Inclusive bounds with exact match

while (lo <= hi) { ... hi = mid - 1; ... lo = mid + 1; }

This is an exact-match search, so inclusive bounds with mid ± 1 are correct — unlike question 4, which is a boundary search and needs half-open bounds with hi = mid. Two rotation problems, two different conventions, decided by whether mid can itself be the answer.

Chained range checks

nums[lo] <= target && target < nums[mid]

Java has no chained comparison, so both halves are written explicitly. && short-circuits, which doesn't matter here since neither side can throw.

6. Interview Communication Guide

Clarifying questions: Distinct values (yes — duplicates break the bound)? Could the rotation be zero (yes)? Return the index or a boolean?

The pitch

"Plain binary search breaks here, because nums[mid] < target doesn't tell me which way to go — the array isn't globally sorted.

But here's the structural fact: wherever I put mid, the pivot falls in one half, which means the other half is entirely inside one sorted run. So at every step, one half is properly sorted.

So it's a two-step decision. First, which half is sorted — I compare nums[lo] against nums[mid]. Second, is the target inside that sorted half's range — which is just a check against its two endpoints, since it's sorted. If yes I search there; if no, the target must be in the other half or absent.

I never reason about the unsorted half. At the next step it'll have its own sorted side.

Two details. I use <= in the sortedness test to cover the two-element case where lo == mid. And the two range checks use different inclusive ends — each uses the closed end of its own half and excludes mid, since mid was already tested for equality.

O(log n) time, O(1) space. And a non-rotated array is handled with no special case — it just always takes the left-sorted branch, which is plain binary search."

Edge cases to volunteer:

[3,1] is the one to name — it's the minimal case where lo == mid, and it's what forces <= rather than < in the sortedness test.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the array contained duplicates?" (LC 81)

nums[lo] <= nums[mid] becomes uninformative when they're equal — [1,1,1,0,1] and [1,0,1,1,1] are indistinguishable at the midpoint. The fix is to advance lo by one and retry, which is safe because nums[lo] is duplicated at mid.

That degrades the worst case to O(n) on an all-equal array. Worth stating plainly: with duplicates the logarithmic bound is simply not achievable, and the return type usually changes to a boolean since a specific index is no longer well-defined.

"Find the minimum instead of a target."

Question 4 — a boundary search comparing against nums[hi], with half-open bounds. Notably a different convention from this problem, because there mid can itself be the answer.

"How many times was the array rotated?"

That's the pivot's index — question 4's answer, returning lo instead of nums[lo].

"What if the array were rotated right instead of left?"

The structure is identical — it's still two sorted runs with everything in the first exceeding everything in the second. A right rotation by k is a left rotation by n − k. No code change.

"What if you had many queries on the same rotated array?"

Find the pivot once in O(log n), then answer each query with plain binary search over the virtual index space using the modulo mapping — O(log n) per query with no repeated pivot search. That's the case where the two-pass approach becomes the better choice, since its setup cost amortizes away.