p33 — Search in Rotated Sorted Array

Source: LeetCode 33 · Medium · Topics: Array, Binary Search Companies (2024–2025 frequency): Meta (very high), Amazon (high), Google (high), Microsoft (high), Apple (high) Loop position: algorithm round. One of the most-asked Mediums in 2024-25. The discriminator: do you write a CLEAN single-pass binary search, or a messy two-pass (find-pivot-then-search)?

1. Quick Context

Given a sorted ascending array of distinct integers nums that has been rotated at an unknown pivot, and a target value, return the index of target if present, else -1. Required: O(log N).

Example: nums = [4,5,6,7,0,1,2], target = 0 → 4. The array was [0,1,2,4,5,6,7] rotated at index 3.

The discriminator: the unwary candidate writes a two-pass solution — binary search to find the pivot, then binary search the right half. Works, but messy. The clean solution is single-pass binary search with a rotation-aware decision rule: at every step, one of the two halves around mid is guaranteed to be sorted (because the rotation creates exactly one discontinuity, and mid is in exactly one half). Determine which, check if target lies in that sorted half, and narrow accordingly.

The invariant: comparing nums[mid] to nums[lo] tells you which half is sorted in one comparison.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/search-in-rotated-sorted-array/

STOP. 25-min timer. The two-pass solution will be marked “works but messy” by Bar Raisers; the single-pass is the senior signal.

3. Prerequisite Concepts

• Plain binary search (LC 704).
• The mental picture: a rotated sorted array is two sorted runs concatenated.
• Off-by-one care with lo, hi, mid, and <= vs <.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Sorted distinct integers, rotated at unknown pivot. Find index of target, O(log N), or -1.”

Step 2 — Clarify:

• “Distinct values?” (Yes for LC 33. LC 81 is the duplicates variant — different problem.)
• “Could the array be unrotated (rotated by 0)?” (Yes — must still work.)
• “Empty array?” (Return -1.)
• “Required O(log N)?” (Yes.)

Step 3 — Constraints: N ≤ 5000 typically, but the O(log N) requirement is the binding constraint. Linear scan is “wrong” even though it’d pass time limits.

Step 4 — Examples:

• [4,5,6,7,0,1,2], target=0 → 4.
• [4,5,6,7,0,1,2], target=3 → -1.
• [1], target=0 → -1.
• [1], target=1 → 0.
• [3,1], target=1 → 1 (rotated at index 1; LEFT half [3] is “sorted” trivially, right half [1] contains target).
• [1,2,3,4,5], target=3 → 2 (unrotated case).

Step 5 — Brute Force: Linear scan O(N). State and pivot to binary search.

Step 6 — Complexity: O(log N) time, O(1) space.

Step 7 — Pattern Recognition:

• “Sorted (possibly transformed) array + need O(log N) lookup” → binary search, possibly with a custom decision rule.
• “Rotated sorted array” → one of the two halves around mid is always sorted. Memorize this invariant.

Step 8 — Develop: see solution.py.

Step 9 — Test: unrotated, rotated by 1, rotated by N-1, single-element, target absent, target at boundaries.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — The “which half is sorted” invariant

6.1 The geometry

A rotated sorted array (distinct values) looks like two ascending runs concatenated, e.g., [4,5,6,7] + [0,1,2]. There is exactly ONE “drop” — between index 3 and index 4 in this example. Anywhere else, nums[i] < nums[i+1].

For any lo <= mid <= hi, the drop is either:

• to the LEFT of mid (somewhere in [lo, mid]), or
• to the RIGHT of mid (somewhere in [mid+1, hi]).

If the drop is to the right of mid, then nums[lo..mid] is sorted (no drop inside it). If the drop is to the left of mid, then nums[mid..hi] is sorted.

6.2 The one-comparison test

How do we tell? Compare nums[mid] to nums[lo]:

• If nums[lo] <= nums[mid], the LEFT half [lo, mid] is sorted. (Because if there were a drop in [lo, mid], then nums[mid] would be less than nums[lo], contradicting nums[lo] <= nums[mid].)
• Else (nums[mid] < nums[lo]), the RIGHT half [mid+1, hi] is sorted.

(The <= matters: when lo == mid, nums[lo] == nums[mid], the left half is trivially sorted — a single element.)

6.3 The narrowing decision

Once we know which half is sorted, we can check if target lies in it via the standard endpoint comparison:

• Left sorted: target is in left iff nums[lo] <= target < nums[mid]. If yes, narrow to left (hi = mid - 1); else, narrow to right (lo = mid + 1).
• Right sorted: target is in right iff nums[mid] < target <= nums[hi]. If yes, narrow to right (lo = mid + 1); else, narrow to left (hi = mid - 1).

6.4 Why this is one-pass

We never explicitly find the pivot. Every iteration halves the search space, just like plain binary search, using a slightly richer decision rule. Total O(log N) — same as plain binary search, with a small constant.

6.5 Duplicates (LC 81)

If duplicates are allowed, the test nums[lo] <= nums[mid] is no longer enough — e.g., nums = [1,1,1,1,1,2,1,1], mid=4. We can’t tell which half is sorted. The fix: when nums[lo] == nums[mid] (and also == nums[hi] for the symmetric case), we can’t decide — increment lo (and/or decrement hi) by 1 and retry. Worst case O(N) on degenerate input.

7. Anti-Pattern Analysis

1. Two-pass solution: find pivot then binary search. Works, twice the code, twice the off-by-one chances. Stick to one-pass.
2. Linear scan. O(N) — violates the requirement.
3. Using nums[hi] instead of nums[lo] as the comparison anchor. Works too, but the case logic is mirrored. Pick one convention and stick to it. Most idiomatic is nums[lo].
4. Forgetting <= in the “is left sorted” test. When lo == mid, you need the equality to handle the single-element left half.
5. Wrong boundary inequality in the “target in sorted half” check. Must use nums[lo] <= target < nums[mid] (not <= nums[mid] — that’s where nums[mid] lives, and we already checked it). Off-by-one nightmare if you get this wrong.
6. Returning mid without first checking nums[mid] == target. That’s literally the first thing inside the loop.
7. Infinite loop via lo = mid (instead of mid+1) when narrowing. With while lo <= hi, always move past mid on narrowing.
8. Conflating LC 33 (distinct) and LC 81 (duplicates). Different problems — different invariants.

8. Skills & Takeaways

• One-pass rotated binary search — burn the template.
• “One half is always sorted” invariant — articulate this clearly to the interviewer.
• nums[lo] <= nums[mid] as the sortedness test — memorize the inequality direction.
• Inclusive bounds (lo, hi) + while lo <= hi — pick a convention and stick.
• Set up for LC 81 (duplicates) and LC 153/154 (find min) as follow-ups.

9. When to Move On

Move on when:

• You can write the single-pass solution in under 8 minutes with correct boundaries.
• You can explain the “one half is sorted” invariant clearly.
• Your stress test passes 300 random rotated arrays vs linear-search oracle.
• You can pivot to LC 81 (duplicates) and explain the worst-case O(N).
• You can pivot to LC 153 (find min) using the simpler version of the same idea (p34).

10. Company Context

Meta:

• Among the top 5 most-asked Mediums in 2024-25 at Meta. The discriminator: clean one-pass binary search with rotation-aware decision rule.
• Bar Raiser asks: “what changes if duplicates are allowed?” (LC 81). Have the answer ready.
• Scorecard phrase: “Algorithm — clean rotated binary search, articulated the sortedness invariant.”

Amazon:

• Common L4/L5 phone screen and onsite. Often paired with LC 153 (find min) in the same loop.
• Scorecard phrase: “Strong — O(log N) on rotated array, clear case analysis.”

Google:

• May extend to LC 81 (duplicates) or LC 4 (median of two sorted arrays) as follow-up — both are binary-search-with-invariants.
• Scorecard phrase: “Algorithm + extension — rotated search + duplicate variant.”

Microsoft:

• Frequent for L62/L63 (mid-senior). The “rotation” framing is a popular wrapper around binary search across multiple Microsoft problem sets.
• Scorecard phrase: “Strong — clean binary search with rotation invariant.”

Apple:

• Often appears in Apple’s “system algorithms” loops. Bar Raiser cares about clarity over cleverness.
• Scorecard phrase: “Solid — readable rotated binary search.”

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• One-pass binary search with rotation-aware decision rule.
• O(log N) time, O(1) space.
• Tests rotated and unrotated, target present and absent.

Senior (L5):

• Same + clean articulation of the invariant (“one half is always sorted”).
• Anticipates the duplicates variant and discusses worst case.
• Discusses why <= vs < matters in the sortedness test.

Staff (L6):

• Connects to LC 81 (duplicates), LC 153 (find min — simpler invariant), LC 4 (median of two sorted arrays — binary search on partition).
• Discusses unification: “all of these are ‘binary search with a custom monotonic predicate’ — the predicate is the design choice.”
• Discusses production: rotating buffer search (ring buffer at unknown rotation offset), log-structured storage with rotation, time-series data after a clock-wrap.

Principal (L7+):

• Discusses branchless binary search for cache-friendly performance (Khuong & Morin 2017, branch predictor effects).
• Discusses parallel binary search for batched queries (multiple targets) — useful in computational geometry.
• Discusses galloping search (exponential then binary) for unknown-position bounded queries — used in Timsort, libstdc++ std::merge.
• Discusses immutable-data system design: this is a search abstraction over an immutable rotated index; in a real system you’d cache the pivot and reuse, or maintain pivot via the same write that caused the rotation.

13. Follow-up Q&A

Q1: What if the array has duplicates? (LC 81) A: The test nums[lo] <= nums[mid] no longer suffices. When nums[lo] == nums[mid], we can’t tell which half is sorted. Workaround: lo += 1 and retry. Worst case O(N) on [1,1,1,...,1,2,1,...].

Q2: Find the rotation pivot index. (LC 153) A: Use while lo < hi: mid = (lo+hi)//2; if nums[mid] > nums[hi]: lo = mid+1 else: hi = mid. Loop ends with lo == hi == pivot index. See p34.

Q3: Find both target’s first and last occurrence in a sorted-non-rotated array. A: Two binary searches with different tie-breaking: one biases left, one biases right. LC 34.

Q4: Search in a rotated 2D matrix (rows individually rotated independently). A: No O(log N·M) trick — each row is its own rotated sorted array; do binary search per row, O(M log N).

Q5: Streaming variant — array is being rotated by writes; queries arrive concurrently. A: Maintain pivot index atomically alongside reads (CAS, RCU, or persistent data structure). The rotation index is a single 64-bit value; updates are cheap; readers compute “logical index” = (physical_index - pivot) mod N.

14. Solution Walkthrough

See solution.py:

• search(nums, target) — one-pass rotated binary search. O(log N).
• search_brute(nums, target) — linear scan. Oracle.
• stress_test() — 300 random sorted arrays (length ≤ 20) rotated by random k, with target in array and target absent.
• edge_cases() — empty, single element, unrotated, rotated by 1 and N-1, target at boundaries, target absent.

Run: python3 solution.py.

15. Beyond the Problem

Principal-engineer code review comment:

“This binary search has FOUR boundary inequalities (<= vs < in two places) plus a (lo + hi) // 2 midpoint — that’s five chances for off-by-one. Write at least one unit test per branch. If you ship this without a stress test against a brute oracle, you will eat a P0 in production. Second: the mid = (lo + hi) // 2 form is fine in Python (arbitrary precision), but in C++/Java/Rust use lo + (hi - lo) // 2 to avoid integer overflow — lo + hi can wrap when both near INT_MAX. This is the canonical Joshua Bloch 2006 bug (‘Nearly All Binary Searches Are Broken’). Third: extract the predicate into a separate function — it makes the case analysis testable in isolation, and it lets you reuse the binary search template for LC 81, LC 153, LC 154. Don’t copy-paste the loop body across problems.”

Connections forward:

• p34 — Find Min in Rotated Sorted Array: same invariant, simpler decision rule.
• p35 — Median of Two Sorted Arrays: binary search on partition (different invariant family).
• LC 81 — Search in Rotated Sorted Array II: duplicates variant.
• LC 154 — Find Min in Rotated Sorted Array II: duplicates variant of p34.
• LC 162 — Find Peak Element: another “binary search with custom invariant.”
• LC 410 — Split Array Largest Sum: binary search on answer (different family — see Phase 02 Lab 04).
• Phase 02 Lab 04 — Binary Search on Answer: dedicated lab.
• Production: rotating-buffer search, time-series data after clock-wrap, log-structured storage indexing.