parikshan

search-in-rotated-sorted-array

Difficulty: Medium  ·  Topic: Binary Search  ·  Practice it on parikshan: /practice/search-in-rotated-sorted-array/start

The story

A SaaS observability backend keeps a fixed-size circular buffer of the last N log entries per tenant, keyed by monotonically increasing sequence number. During a high-traffic minute the buffer wrapped: the physical array now holds, in order, the tail of an older window followed by the head of a newer window. Sequence numbers are still strictly increasing within each half, but the array as a whole is a rotated sorted array. Support asks "fetch entry with sequence number X" and the answer must come back in O(log n) regardless of where the wrap landed. Linear scans across millions of entries per tenant are off the table.

search-in-rotated-sorted-array is the canonical version of that lookup. It builds directly on find-min-in-rotated-sorted-array but adds one wrinkle: you are searching for a value, not the minimum. The trick that solves it cleanly is the "which half is sorted" predicate.

What's actually being asked

You are given an array of distinct integers that was sorted ascending then rotated by an unknown amount, plus an integer target. Return the index of target in the array, or -1 if it is absent. Run in O(log n).

The naive approach

nums.index(target). O(n). Same problem as before: at a million elements per lookup, the matching engine is dead.

A slightly smarter naive: binary-search for the rotation point (find-min-in-rotated-sorted-array), then binary-search either side based on whether target <= nums[-1]. Two passes, both O(log n). Correct, but it does double the work. The single-pass version is cleaner and faster.

The key insight

At any midpoint mid of a rotated sorted array, at least one of the two halves [lo..mid] and [mid..hi] is itself a strictly sorted (non-rotated) slice. You cannot fit two rotation points into one cut; the pivot lives in exactly one half, and the other half is untouched.

So the algorithm becomes:

  1. Pick the midpoint. If nums[mid] == target, done.
  2. Detect which half is sorted by comparing nums[lo] with nums[mid]. If nums[lo] <= nums[mid], the left half is sorted; otherwise the right half is sorted.
  3. On the sorted half, use a plain range check (is target in [nums[lo], nums[mid])?). If yes, recurse into it. If no, the target must be in the other half (the one that contains the pivot).

This is what makes the problem feel mechanical once you see it: every iteration, the sorted half is the easy half, and the other half is "everything we have not ruled out yet".

Step-by-step approach

def search(nums, target):
    lo, hi = 0, len(nums) - 1          # closed window
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:      # LEFT half [lo..mid] is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1           # target is in the sorted left half
            else:
                lo = mid + 1           # target is in the (possibly rotated) right half
        else:                          # RIGHT half [mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1           # target is in the sorted right half
            else:
                hi = mid - 1           # target is in the (possibly rotated) left half
    return -1

Loop invariant in English: if target is in the array, it is somewhere in nums[lo..hi] (closed). The window shrinks by at least one each iteration; the loop runs O(log n) times.

The closed-form template (while lo <= hi) is the natural fit here because the answer is an index that must EXIST in the array; "lo == hi" is the last viable single-cell window to check.

Worked example

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
  • lo=0, hi=6. mid=3, nums[3]=7. 7 ≠ 0. nums[0]=4, 4 ≤ 7 → LEFT half [0..3]=[4,5,6,7] is sorted. Is 0 in [4, 7)? No. → lo=4.
  • lo=4, hi=6. mid=5, nums[5]=1. 1 ≠ 0. nums[4]=0, 0 ≤ 1 → LEFT half [4..5]=[0,1] is sorted. Is 0 in [0, 1)? Yes → hi=4.
  • lo=4, hi=4. mid=4, nums[4]=0. 0 == 0 → return 4. ✓

Counter-case: same array, target = 3. The search follows the same path but every range check fails until lo > hi. Return -1.

Counter-case: nums = [1], target = 0. lo=0, hi=0, mid=0, nums[0]=1 ≠ 0, range check fails → lo=1 (since left half is trivially sorted, 0 not in [1, 1)). Loop exits. Return -1.

Complexity

  • Time: O(log n).
  • Space: O(1).

Common pitfalls

  1. Inclusive vs exclusive on the sorted-half range check. The check nums[lo] <= target < nums[mid] uses < on the right because nums[mid] was already tested as the answer in the previous line and is ruled out. Mixing <= and < is the most common silent bug; one extra equality and the algorithm loops or misses.
  2. nums[lo] <= nums[mid] vs <. With distinct elements either works, but consistency matters. The <= form is conservative; it handles the degenerate lo == mid case (length-1 window) without a separate branch.
  3. Forgetting the nums[mid] == target short-circuit. Without it the range-check logic can move mid out of the window and the answer is missed.
  4. Using the find-min two-pass approach by reflex. Correct, but with twice the constant factor and twice the surface area for off-by-ones. Single-pass is the canonical form.
  5. Handling duplicates accidentally. The variant search-in-rotated-sorted-array-ii allows duplicates and forces a worst-case O(n) when nums[lo] == nums[mid]. This problem guarantees distinct values, so the strict logic is safe.

Where this shows up in the enterprise

  • Fixed-size ring buffers (telemetry, audit, observability): a sequence-keyed lookup over a buffer that wrapped is exactly a rotated-sorted-array lookup; the rotation point is the write head.
  • Date-rotated reports: monthly or yearly statements presented "current period first, prior periods after" so the time-sorted column is rotated by one cut. Lookup by date is this template.
  • Log files concatenated after a rollover: when an operator stitches two retention windows tail-to-head for a single search, the union is rotated-sorted.
  • Carousel-style UIs over sorted data: news, photos, or calendar entries displayed starting from a user-selected anchor and wrapping the rest around it; jump-to-entry is binary search on a rotated view.
  • Embedded sensor logs with bounded flash: oldest-overwritten-first storage; the on-disk layout is a rotation of the sequence-sorted log.
  • Backup snapshot indices: when a manifest lists snapshots starting from the most recent and wrapping older ones around, a lookup-by-timestamp resolves to this template.

Anywhere a sorted sequence has been cut and rotated, search-in-rotated-sorted-array is the lookup. The honest caveat: most production logs are monotone, not rotated. Rotation requires the underlying values to be sorted, then the sorted sequence to be cut and rearranged once. When you spot that fingerprint, the algorithm is in your hand.

Variants you'll see elsewhere

  • find-min-in-rotated-sorted-array: the prerequisite. Locates the rotation point.
  • search-in-rotated-sorted-array-ii: allows duplicates. Worst-case O(n).
  • search-2d-matrix: same template against a row-major sorted 2D array, treated as 1D.
  • find-peak-element: the "which half is sloping up" predicate is a cousin of the "which half is sorted" predicate.
  • kth-smallest-in-sorted-matrix: binary-search the answer space and count cells; conceptually different but the same template scaffold.

How parikshan turns this into a learning loop

This is the problem where students who memorised binary search fall over. Recommended sequence on parikshan:

  1. Solve find-min-in-rotated-sorted-array first. That gets the rotation intuition into your hands.
  2. In practice mode, AI off, draw [4, 5, 6, 7, 0, 1, 2] on paper. Pick a target. By hand, identify the sorted half. Then pick the unsorted half and recurse.
  3. Code the template. Run public tests. The dynamic private tests generated per session will throw rotated-by-zero, rotated-by-n-1, length-1, and a target equal to the rotation point. Wrong templates fail at least one.
  4. If you fail, trace by hand first, not by asking AI. The bugs in this problem are almost always in the range-check inequalities; the agent will rewrite the function and confuse the issue.

The integrity score weights "submissions that earned AC without AI" higher. That is not a moral judgment; it is a signal that you have the template in your fingers, which is the only signal that matters when you walk into an interview.

In the AI-integrated workspace

Of all the binary-search problems in this catalog, this is the one where AI-generated code goes wrong most often. The two failure modes:

  1. Inverted predicate: the agent checks nums[mid] <= nums[hi] (find-min style) instead of nums[lo] <= nums[mid]. The code looks right and runs fine on the rotated sample input. It fails on the non-rotated case.
  2. Off-by-one in the range check: nums[lo] <= target <= nums[mid] (with <= on both sides) overlaps with the nums[mid] == target short-circuit and either loops or returns wrong.

Verification ritual on every agent-generated rotated-search:

  1. Ask the agent to trace the function by hand on [3, 1] with target=1. Length-2 is the smallest case where rotation matters. Wrong templates die here.
  2. Ask "what does the function return on [1] with target=0?" Must be -1 in one iteration.
  3. Read the range check. There must be exactly one < and one <= per branch, and they must be consistent with the short-circuit.

Engineers who can run this ritual unprompted are the ones whose code stays correct through every rotation amount the buffer can land on, including the unrotated and one-off edge cases. parikshan drills it.