Search in Rotated and 2D Arrays

Binary search extends to trickier sorted structures: a rotated sorted array (sorted then shifted) and a 2D matrix with sorted rows/columns. Both keep the O(log n)-style efficiency, but require an extra observation about which half or direction is ordered.

The core idea

• Rotated sorted array: at each step, one half [lo, mid] or [mid, hi] is still sorted. Determine which (compare endpoints), check if the target lies within that sorted half, and recurse into the right half — O(log n). Duplicates can degrade it to O(n).
• 2D matrix, fully sorted (each row sorted, first of a row > last of previous): treat it as a flattened sorted array and binary search in O(log(m·n)).
• 2D matrix, row- and column-sorted only: start at the top-right corner; move left if larger, down if smaller — O(m + n).

Structure	Method	Time
Rotated sorted array	find sorted half	O(log n)
Rotated with duplicates	may need linear scan	O(n) worst
Fully sorted matrix	flatten + binary search	O(log(m·n))
Row/col-sorted matrix	top-right staircase	O(m + n)

Exam Tricks & Tips

• 🎯 Rotated array: identify which half is sorted, then check if the target is inside it.
• 🎯 Find the rotation/pivot point with binary search (min element) in O(log n).
• 🎯 Fully sorted matrix → map index k to (k / cols, k % cols) and binary search in O(log(m·n)).
• 🎯 Row/col-sorted matrix → start top-right (or bottom-left), staircase in O(m + n).
• 🎯 Duplicates in a rotated array can force O(n) — mention this caveat.
• ❌ Common mistake: assuming a row/col-sorted matrix is fully sorted and applying a single binary search (wrong).

Expected pattern

Search in a rotated sorted array (with/without duplicates), find minimum in a rotated array, search a 2D matrix (both variants), or Kth smallest in a sorted matrix. Interviewers check the "which half is sorted" logic and the two matrix models.

Quick recap

Rotated array search finds the sorted half and checks the target against it — O(log n) (O(n) with duplicates). Fully sorted matrix → flatten and binary search O(log(m·n)); row/col-sorted matrix → top-right staircase O(m + n).

Cover the answer, recall, then check. 11 cards on searching rotated and 2D arrays.

Q1. Search a rotated sorted array — key observation?
A1. At any split, at least one half [lo,mid] or [mid,hi] is still fully sorted.

Q2. Complexity of rotated-array search (no duplicates)?
A2. O(log n).

Q3. How do duplicates affect rotated-array search?
A3. They can force a linear scan, degrading to O(n) worst case.

Q4. Find the minimum in a rotated sorted array — approach?
A4. Binary search for the pivot: compare mid with hi to decide which half holds the minimum. O(log n).

Q5. Search a fully sorted matrix efficiently?
A5. Treat it as a flattened sorted array; binary search with index → (k/cols, k%cols). O(log(m·n)).

Q6. Search a row- and column-sorted (but not fully sorted) matrix?
A6. Start at the top-right: move left if the value is larger, down if smaller. O(m + n).

Q7. After finding the sorted half, what do you check?
A7. Whether the target lies within that half's range; if so search it, else search the other half.

Q8. Why does top-right work for a staircase search?
A8. From there, one direction strictly increases and the other strictly decreases, giving a unique move each step.

Q9. Kth smallest in a sorted matrix — one method?
A9. Binary search on the value range with a count of elements ≤ mid. O(n log(range)).

Q10. Common mistake conflating the two matrix models?
A10. Applying a single O(log(m·n)) binary search to a matrix that's only row/col-sorted, not fully sorted.

Q11. Complexity of the staircase search in the worst case?
A11. O(m + n) — you move left or down at most m + n times total.

Two binary-search variants show up constantly: searching a rotated sorted array and searching a sorted 2-D matrix. Both keep the O(log n) magic by cleverly deciding which half (or which direction) to discard.

Core idea: binary search works whenever you can decide, in O(1), which side of the middle to keep. A rotated array still has one sorted half at every step; a sorted matrix can be treated as one long sorted list or navigated from a corner.

How it works

Beginner — rotated sorted array

A rotated sorted array (e.g. [4,5,6,7,0,1,2]) has a pivot, but at any mid one half is fully sorted. Check which, then decide if the target lies in it:

while lo <= hi:
    mid = (lo + hi)//2
    if a[mid] == target: return mid
    if a[lo] <= a[mid]:                 # left half sorted
        if a[lo] <= target < a[mid]: hi = mid-1
        else: lo = mid+1
    else:                              # right half sorted
        if a[mid] < target <= a[hi]: lo = mid+1
        else: hi = mid-1

O(log n) — still logarithmic despite the rotation.

Intermediate — search a sorted matrix

• Fully sorted matrix (each row sorted, first of each row > last of previous): treat the m×n grid as one sorted array of length m·n and binary-search, mapping index → (index // n, index % n) → O(log(m·n)).
• Row- and column-sorted matrix (weaker): start at the top-right corner; move left if too big, down if too small → O(m + n) (the staircase search).

Advanced — duplicates and finding the pivot

• With duplicates in a rotated array ([2,2,2,0,2]), you can't always tell which half is sorted when a[lo] == a[mid]; shrink lo++ in that case, degrading to O(n) worst case.
• Find the rotation point (minimum element) by binary-searching for where a[mid] > a[hi] (minimum is to the right) — useful for "find min in rotated array".

Worked example

Search 0 in [4,5,6,7,0,1,2]. lo=0,hi=6,mid=3 → a[3]=7≠0. Left half a[0..3]=[4,5,6,7] sorted; is 0 in [4,7)? No → search right, lo=4. mid=5 → a[5]=1≠0; left half a[4..5]=[0,1] sorted; is 0 in [0,1)? Yes → hi=4. mid=4 → a[4]=0 → return index 4. O(log n) even with the rotation.

When to use it

• Rotated sorted array: search, find minimum, find rotation count (common at top companies).
• Sorted matrix search: "search a 2-D matrix", "Kth smallest in sorted matrix" (with binary-search-on-value).
• Any "sorted but transformed" structure where one half/direction stays ordered.

Tricks & gotchas

• In a rotated array, first determine which half is sorted (a[lo] <= a[mid]), then test if the target lies within that sorted half's range.
• For a fully-sorted matrix, index-map to O(log(m·n)); for row/col-sorted, use the O(m+n) corner walk — don't confuse the two matrix types.
• Duplicates break the "which half is sorted" test → O(n) worst case.
• Mnemonic: "One half is always sorted — decide, then discard the other."

Worked Example

Problem: Find the index of 0 in the rotated sorted array [4, 5, 6, 7, 0, 1, 2] using modified binary search.

Solution: In a rotated sorted array, at least one half around mid is still sorted. Identify the sorted half, check if the target lies within it, and recurse accordingly.

lo	hi	mid	a[mid]	sorted half	target 0 in it?	move
0	6	3	7	left [4..7] sorted	0 not in [4,7]	lo = 4
4	6	5	1	left [0..1] sorted (a[4]=0 ≤ 1)	0 in [0,1]	hi = 4
4	4	4	0	—	equal	found!

Target 0 is at index 4.

Still O(log n), since each step discards half the array despite the rotation.

Answer: Found at index 4.