Search in Rotated Sorted Array — The Shifted Vault Codes · DSA Quest

5Search in Rotated Sorted Array — The Shifted Vault Codes

Four bosses down

Last boss, you untangled Nadia's rotated logbook and pinned the minimum at the pivot. Good, because this boss is the same rotated mess with higher stakes. You're not looking for the smallest value anymore. You're hunting one specific value inside the spin.

Today's boss: The Shifted Vault Codes.

The story

Meridian Bank, 2 a.m. The vault prints its rotating access codes every night as a single sorted list. Tonight the printer jammed halfway, someone re-fed the paper, and the list came out rotated. Same binder accident energy as last boss.

The security chief, Idris, slaps the printout on the desk. A test strip on top reads:

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

"Silent alarm just tripped," he says. "Someone punched in code 0 at the side door. I need to know if 0 is even on tonight's sheet, or if we've got a forged code. You have thirty seconds, and the real sheet has 10,000 codes."

Thirty seconds. Ten thousand lines. Reading every line is not happening.

The problem, dressed up properly

There is an integer array nums sorted in ascending order with distinct values. Prior to being passed to your function, nums is possibly rotated at an unknown pivot index.

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not.

You must write an algorithm with O(log n) runtime complexity.

That's LeetCode 33, Search in Rotated Sorted Array. Medium, and a genuine interview classic.

The naive attempt

Panic mode says scan the sheet top to bottom:

def search(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1

O(n). For 10,000 codes at human reading speed, Idris's thirty seconds are long gone. And plain Binary Search won't run as-is, because the rotation broke the single sorted line it depends on. Aim for the middle of [4, 5, 6, 7, 0, 1, 2] hunting 0, and the usual "target smaller than mid, go left" logic walks you straight away from it.

But you cleared Boss 4. You know this array isn't chaos. It's two sorted runs. There has to be a way to cut it in half anyway.

The weapon: one half is always sorted

Here's the observation that cracks the vault. Pick any mid in a rotated sorted array. The pivot, the one place where order breaks, lives on one side of mid. Which means the other side is a perfectly sorted run. Every single time.

[4, 5, 6, 7, 0, 1, 2]
          ^
         mid
 [4,5,6,7] sorted     [0,1,2] also fine here

So at every step, ask two questions:

Question 1: which half is sorted? If nums[lo] <= nums[mid], the left half climbs smoothly from lo to mid. Otherwise the pivot is in the left half, so the right half is the sorted one.

Question 2: is the target inside the sorted half's range? A sorted half is the only region you can interrogate with a simple range check. If target falls between its endpoints, go there. If not, the target must be in the other, messier half. Toss the sorted half and recurse into the mess.

Either way, half the sheet is gone. That's Binary Search with one extra question bolted on.

Watching it work

Hunt target = 0 in [4, 5, 6, 7, 0, 1, 2]:

step  lo  hi  mid  nums[mid]  which half sorted?      target in it?         move
1     0   6   3    7          nums[0]=4 <= 7 → left   0 in [4..7)? no       lo = 4
2     4   6   5    1          nums[4]=0 <= 1 → left   0 in [0..1)? yes      hi = 4
3     4   4   4    0          nums[4] == 0 → found, return 4  ✓

Three steps for seven codes. For the full 10,000-code sheet, about 14. Idris gets his answer with twenty seconds to spare: code 0 is real, index 4, no forgery.

Look at step 2 for a second. The "left half" was just [0, 1], two elements, and the range check 0 <= 0 < 1 calmly pointed left. The logic doesn't care how lopsided the halves get.

The code

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
 
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
 
        if nums[lo] <= nums[mid]:            # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1                 # target inside it
            else:
                lo = mid + 1                 # target in the other half
        else:                                # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1                 # target inside it
            else:
                hi = mid - 1                 # target in the other half
 
    return -1

Unlike last boss, this is the classic while lo <= hi template with an early return, because we're hunting an exact value that might not exist. The only new muscle is the sorted-half check wrapping the range test.

The two-pass alternative

You could also solve this with tools you already own. Pass one: find the pivot with Boss 4's technique. Pass two: the pivot splits the array into two sorted runs, so pick the run whose range covers target and hit it with vanilla Binary Search. Two O(log n) passes, still O(log n) total, completely legitimate.

So why bother with one-pass? Because in an interview, the one-pass version shows you actually understand why the rotation is survivable, not just that you can chain two memorized routines. It's less code, one loop, no pivot bookkeeping. That's the flex.

Gotchas

1. The <= in nums[lo] <= nums[mid] matters. When the window shrinks to where lo == mid, the "left half" is a single element, and a single element is sorted. With a strict < you'd misclassify it, branch into the wrong half, and miss targets on two-element windows like [3, 1]. Equality must count as sorted.

2. Get the range checks' strictness right. nums[lo] <= target < nums[mid] is strict on the mid side because nums[mid] == target already returned. Make it <= on both ends and you'll loop on windows that should shrink.

3. Don't forget the miss case. The loop can exhaust without finding anything. Hunting a forged code that isn't on the sheet must return -1, not crash or loop forever. while lo <= hi with mid ± 1 moves guarantees termination.

4. Duplicates break it. With distinct values, nums[lo] <= nums[mid] cleanly identifies the sorted half. Allow duplicates and nums[lo] == nums[mid] becomes ambiguous, which is LeetCode 81 territory with an O(n) worst case.

Complexity

Time: O(log n). One extra comparison per step, still half the codes discarded each round.
Space: O(1).

Boss down. XP gained.

What you walked away with:

At any mid of a rotated sorted array, one half is guaranteed sorted
Identify it with nums[lo] <= nums[mid], then range-check the target against the sorted half only
One-pass beats two-pass in an interview, even though both are O(log n)

Next up: Boss 6 — The Ticker Tape. A key-value store where every write is stamped with a timestamp, and reads ask "what was the value at time t?" Binary Search is about to leave arrays behind and start searching time itself.