Search in a Rotated Sorted Array with Binary Search

01 · Strip it down

A sorted array, shifted, then searched in O(log n)

A sorted array like [0,1,2,4,5,6,7] gets rotated to [4,5,6,7,0,1,2]. Given the rotated array and a target, find its index (or −1) in O(log n). The log-n requirement screams binary search — but the array isn't globally sorted anymore, so plain binary search won't work as-is.

Why plain binary search breaks At mid=3, nums[mid]=7, target 0: since 0 < 7, ordinary binary search goes left — but 0 is on the right. Comparing target to nums[mid] alone is no longer enough.

02 · What survives the rotation

One break, so one half stays sorted

A rotated sorted array is just two increasing runs stitched together — [4,5,6,7] | [0,1,2] — with a single "break" where a high value drops to a low one (7 → 0). That break lives in only one half around any midpoint, so the other half must still be perfectly sorted.

Detecting the sorted half With distinct values, nums[left] ≤ nums[mid] means the left half is sorted (no break wrapped it). Otherwise the break is on the left, so the right half is sorted.

03 · The two-layer decision

Which half is sorted, then does the target live there?

Finding the sorted half isn't enough — the target might not be in it. So each step asks two questions, and only a sorted half lets you range-check reliably (its ends bound every value inside).

Left half sorted

nums[left] ≤ target < nums[mid]

In range → go left (right=mid−1). Else go right.

Right half sorted

nums[mid] < target ≤ nums[right]

In range → go right (left=mid+1). Else go left.

mid is excluded from both ranges because it was already checked for equality. Either way, one half is provably discarded — so the search space still halves every step, keeping it O(log n).

A clock with one seam

Numbers still climb around the dial; there's just one seam where 12 meets 1. Any arc you pick that avoids the seam reads in perfect order.

Cut a deck of cards

Cutting a sorted deck moves a block from top to bottom. Each block is still internally in order — you just have to notice which side the cut landed on.

Trust the tidy room

Of two rooms, one is always tidy (sorted). Check if your item belongs in the tidy room's range; if not, it must be in the messy one.

04 · Watch it search

Sorted half in teal, the break-half in terracotta

Set a rotated array and target, then step. Each step highlights mid, colors the sorted half teal and the break-half terracotta, and shows whether the target falls in the sorted half's range — then discards a half. The match locks in solid teal.

Rotated-array search

target

sorted half break half mid

Try 6 7 0 1 2 4 5 target 4 (right half sorted), 1 2 3 4 5 target 4 (no rotation), or 3 1 target 1 (tiny edge case).

05 · Trace table

Finding 0 in [4,5,6,7,0,1,2]

left	mid	right	nums[mid]	Sorted half	Decision
0	3	6	7	left [4,7]	0 not in [4,7) → go right
4	5	6	1	left [0,1]	0 in [0,1) → go left
4	4	4	0	—	found → index 4

Five things to log when debugging any rotated search: left, mid, right, which half is sorted, and the target-range decision. The bug is almost always in the last two.

06 · The code

One binary search, one extra question

int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {              // left half sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                  // right half sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Constant work per step, half discarded each time → O(log n) time, O(1) space. Note the asymmetric bounds (<= on the sorted end, < next to mid) — mid is already handled by the equality check, so both ranges exclude it.

07 · Two things worth noting

Why "distinct" matters, and the pivot alternative

Distinct values isn't decoration

[1,1,1,3,1]

With duplicates, nums[left] == nums[mid] can't tell you which side holds the break — that's the harder "II" variant. Uniqueness is what keeps this O(log n).

Pivot-first alternative

find min, then search

Binary-search the rotation point, then run a normal search in the correct run. Also O(log n), but two passes — the one-pass version is cleaner when you only need the target.

Solve only what the next decision needs You never actually locate the pivot here. Reasoning locally — "which half is sorted?" — gives just enough to discard a half, without solving the harder pivot subproblem first.

08 · Traps to avoid

Four ways it goes wrong

Comparing to mid only

Treating it like a normal sorted array (target < nums[mid] → go left) ignores rotation. First find the sorted half.

Sorted half, wrong turn

Finding the sorted half doesn't mean search it. [4,5,6,7,0,1,2], mid=7: left is sorted but 0 isn't there — range-check first.

Range inclusivity slips

Left: nums[lo] ≤ t < nums[mid]. Right: nums[mid] < t ≤ nums[hi]. Off-by-one here is the classic bug.

Scan or re-sort

A linear scan is O(n); sorting is O(n log n) and loses indices. Both miss the point and violate O(log n).

09 · The pattern

Binary search needs structure, not full sortedness

The lazy rule "sorted array → binary search" is too narrow. The real requirement: a reliable way to prove one half can't contain the answer. Full sortedness is one way to get that; a rotated array's guaranteed-sorted half is another.

First/last position

fully sorted

lean toward the boundary among duplicates

Rotated search

one half sorted

recover local order to discard a half

Both halve the space each step because both supply enough monotonic structure to eliminate candidates — even though only one of them looks sorted.

10 · One month from now

Reconstruct it, don't memorize it

The array was sorted, then rotated — so there's exactly one break in order.
Around any mid, one half avoids the break and stays sorted.
Detect it: nums[left] ≤ nums[mid] → left sorted, else right sorted.
If the target is inside that sorted half's range, search there.
Otherwise search the other half. Repeat like binary search.

The transferable insight Binary search doesn't require the whole input to look sorted — it requires a rule that proves one half can't hold the answer. Rotation destroys global order but preserves enough local order (one sorted half) to keep the O(log n) elimination alive.