Rotated and 2D Arrays

What is this?

Take a sorted list of names on a rolodex and spin it so it now starts partway through the alphabet. Global order is gone — but the structure is not random. Open it anywhere and at least one side of where you are looking is still in proper order. Work out which side that is, decide whether your target lives there, and you have discarded half the rolodex with one comparison.

Then a second question: what if some names repeat so often that you cannot tell which side is sorted?

flowchart TD A["window [lo, mid, hi]"] --> B{"nums[lo] vs nums[mid]"} B -->|"nums[lo] < nums[mid]"| C["LEFT half is sorted"] B -->|"nums[lo] > nums[mid]"| D["RIGHT half is sorted"] B -->|"equal — duplicates"| E["cannot tell
shrink lo by one and retry"] C --> F["is the target inside the sorted half?
yes → search it, no → search the other"] D --> F E --> G["worst case O(n)"]

💡 Fun fact: Search a 2D Matrix II — rows sorted left to right, columns sorted top to bottom — has a solution that is not binary search at all, and is both faster to write and easier to justify. Start at the top-right corner. If the value is too big, no cell below it in that column can help, so delete the column. If it is too small, no cell to its left in that row can help, so delete the row. Every comparison removes an entire row or column, giving O(m + n). The corner works because it is the only position where the two comparisons point in unambiguous, opposite directions.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: a rotated array is two sorted runs joined at a seam, so one half of any window is always properly sorted — find it, test whether the target lies inside it, and discard the other half. Duplicates can hide which half that is, and that is what costs you the logarithm.

1. Identify the sorted half

while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target:
        return True
    if nums[lo] < nums[mid]:                       # left half is sorted
        if nums[lo] <= target < nums[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    elif nums[lo] > nums[mid]:                     # right half is sorted
        if nums[mid] < target <= nums[hi]:
            lo = mid + 1
        else:
            hi = mid - 1
    else:                                           # nums[lo] == nums[mid]: ambiguous
        lo += 1                                     # shrink and retry

Comparing nums[lo] with nums[mid] is what identifies the sorted half. The target test then happens inside that half, where an ordinary range check is valid; you can never reason about the unsorted half directly.

The third branch is the honest one. When nums[lo] == nums[mid] you genuinely cannot tell which side holds the seam — [1,1,1,2,1] and [1,2,1,1,1] look identical from lo, mid and hi. The only safe move is to shrink the window by one, which makes the worst case O(n). Say that out loud rather than pretending the solution stays logarithmic.

2. Finding the minimum

Find Minimum in Rotated Sorted Array II compares nums[mid] with nums[hi] instead — and the choice of pivot matters:

nums[mid] > nums[hi] → the seam is to the right, so lo = mid + 1
nums[mid] < nums[hi] → mid could itself be the minimum, so hi = mid
nums[mid] == nums[hi] → ambiguous, so hi -= 1 (safe, because if nums[hi] were the minimum then nums[mid] equals it anyway)

Comparing against nums[lo] instead needs an extra special case for the not-rotated-at-all array. This is one of those problems where choosing the right thing to compare against deletes a whole branch.

3. The staircase

For the matrix, forget binary search:

matrix:                target = 5, start at top-right
 1  4  7 11 15
 2  5  8 12 19         15 > 5 → drop that column
 3  6  9 16 22         11 > 5 → drop that column
10 13 14 17 24          7 > 5 → drop that column
18 21 23 26 30          4 < 5 → drop that row
                        5 == 5 → found ✓

Each step eliminates a full row or column, so at most m + n steps. Starting from the top-left would not work: both "right" and "down" increase, so a too-small value gives you no way to choose between them.

4. Where you'll actually meet this

Log and buffer search. Circular buffers wrap, so searching one by timestamp is a rotated-array search.
Sharded and rotated indexes. Consistent-hashing rings are sorted-then-rotated by construction.
Version and release history. Finding where a wrapped sequence restarts is seam-finding.
Spreadsheet and grid queries. Doubly-sorted tables are searched with the staircase walk in real products.
Image processing. Threshold searches over intensity maps that are monotone in both axes use the same corner walk.

5. Problems in this chapter

▶ Find Minimum in Rotated Sorted Array II

Find the smallest value in a rotated array that may contain duplicates. Compare mid against hi; on equality shrink hi by one.
Pattern: seam search with a safe tie-break. Target: O(log n) average, O(n) worst case.

▶ Search in Rotated Sorted Array II

Decide whether a target exists in a rotated array with duplicates. Identify the sorted half, test the target against it, shrink on ambiguity.
Pattern: sorted-half identification. Target: O(log n) average, O(n) worst case.

▶ Search a 2D Matrix II

Search a matrix whose rows and columns are both sorted. Walk the staircase from the top-right corner.
Pattern: corner elimination. Target: O(m + n) time, O(1) space.

6. Common pitfalls 🚫

Testing the target against the unsorted half. The range check is only valid inside the half you have proven is sorted.
Folding the equality case into "left is sorted". With duplicates present, nums[lo] == nums[mid] must have its own branch.
Claiming O(log n) with duplicates. The worst case is genuinely linear; explain why instead of hiding it.
Comparing against nums[lo] when finding the minimum. It works, but needs an extra case for the un-rotated array.
Using hi = mid - 1 when mid might be the answer. For minimum-finding, mid is still a candidate, so hi = mid.
Starting the matrix walk at the top-left or bottom-right. Both comparisons point the same way there, so nothing can be eliminated.
Treating the matrix as one long sorted array. That works only for the other matrix problem, where each row starts after the previous row ends.

7. Key takeaways

A rotated array is two sorted runs. One half of any window is always properly sorted — identify it first.
Reason only inside the sorted half. Everything else is guesswork.
Duplicates cost you the logarithm, and the right response is to acknowledge it and shrink by one.
Choose the comparison pivot deliberately — mid against hi removes a special case that mid against lo requires.
hi = mid when mid is still a candidate, hi = mid - 1 only once it is ruled out.
The staircase beats binary search on a doubly-sorted matrix — O(m + n), simpler, easier to justify.
Why interviewers like it: these reward precision about invariants and punish pattern-matching. The duplicate case in particular separates understanding the guarantee from memorising the loop.

Order: Find Minimum in Rotated Sorted Array II → Search in Rotated Sorted Array II → Search a 2D Matrix II.

Single Element in a Sorted Array, the parity-search warm-up, is in Coding Interview 101.

Intermediate