Loading learning content...
Imagine you're given a sorted array that has been rotated at some unknown pivot point. What was once [1, 2, 3, 4, 5, 6, 7] might now be [4, 5, 6, 7, 1, 2, 3]. The array is still "mostly sorted"—but standard binary search would fail catastrophically.
This is one of the most celebrated problems in algorithm interviews: it appears constantly at Google, Amazon, Meta, and virtually every top tech company. It tests not just whether you know binary search, but whether you understand it deeply enough to adapt it to a twisted scenario.
The key insight that unlocks this entire problem class is deceptively simple: in any rotated sorted array, at least one half is always perfectly sorted. Once you internalize this observation, the problem transforms from bewildering to tractable.
By the end of this page, you will understand the fundamental structure of rotated arrays, why one half is always sorted, and how to identify which half is the sorted portion using a simple O(1) check. This insight is the foundation for all rotated array search strategies.
A rotated sorted array is a sorted array that has been pivoted around some index. Think of it like taking a sorted deck of cards, cutting the deck somewhere in the middle, and placing the bottom portion on top.
Formal definition:
Given a sorted array A of n distinct elements, rotating it by k positions produces an array where:
A[k], A[k+1], ..., A[n-1] appear first (in order)A[0], A[1], ..., A[k-1] appear after (in order)The rotation "wraps around" the array, creating exactly two sorted subsequences.
Original sorted array: [1, 2, 3, 4, 5, 6, 7]Rotation k=0: [1, 2, 3, 4, 5, 6, 7] — No rotation (still fully sorted)
Rotation k=1: [7, 1, 2, 3, 4, 5, 6] — Last element moves to front
Rotation k=2: [6, 7, 1, 2, 3, 4, 5] — Last two elements move to front
Rotation k=3: [5, 6, 7, 1, 2, 3, 4] — Last three elements move to front
Rotation k=4: [4, 5, 6, 7, 1, 2, 3] — Classic example from most textbooks
Rotation k=7: [1, 2, 3, 4, 5, 6, 7] — Full rotation = back to originalNotice that each rotated array contains exactly two sorted runs. The 'break point' is where the larger value is followed by a smaller value—this is the rotation point.
The rotation point (also called the pivot) is the index where the rotation occurred. It's the location where arr[i] > arr[i+1], creating a 'cliff' in the otherwise ascending sequence. In [4, 5, 6, 7, 1, 2, 3], the rotation point is at index 3 (value 7), because 7 > 1.
Real-world interpretation:
Rotated arrays appear in practice more often than you might expect:
The core challenge is that you can't immediately apply binary search because the normal assumption (arr[low] ≤ arr[high]) no longer holds across the entire array.
Here is the critical insight that transforms rotated array search from impossible to elegant:
In any rotated sorted array divided at its midpoint, at least one of the two halves is guaranteed to be perfectly sorted.
This is not a heuristic or approximation—it's a mathematical certainty. Understanding why this holds is essential for internalizing the algorithm.
Because a rotated sorted array contains exactly two sorted runs, and these runs are contiguous, the rotation point can only be in one half at a time. The half without the rotation point is completely sorted. The half with the rotation point contains elements from both sorted runs, but is 'broken' by the pivot.
Rigorous proof:
Let the array have n elements with rotation point at index p. When we compute mid = (low + high) / 2:
Case 1: The rotation point p is in the right half (p > mid)
[low..mid] contains only elements from the second sorted runCase 2: The rotation point p is in the left half (p ≤ mid)
[mid..high] contains only elements from the first sorted run (post-rotation)Case 3: The array is not actually rotated (or rotated n times)
In all cases, at least one half is sorted. This is the invariant we exploit.
Now that we know one half is always sorted, how do we determine which half? The answer is remarkably simple—we only need to compare the first and middle elements.
The identification rule:
[low..mid] is sorted. This is because in a sorted sequence, the first element must be ≤ the middle element.[mid..high] is sorted. The left half contains the rotation point, so the right half must be the clean sorted portion.We use ≤ (less than or equal) rather than < (strictly less than) to handle the edge case where low = mid (when the subarray has only 1-2 elements). In this case, arr[low] = arr[mid], and the 'left half' (just one element) is trivially sorted.
Walking through the logic:
Consider arr = [4, 5, 6, 7, 1, 2, 3] with low = 0, high = 6, mid = 3:
arr[0] ≤ arr[3]? Is 4 ≤ 7? Yes[4, 5, 6, 7] is sortedNow consider arr = [5, 6, 7, 1, 2, 3, 4] with low = 0, high = 6, mid = 3:
arr[0] ≤ arr[3]? Is 5 ≤ 1? No[1, 2, 3, 4] is sorted1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
def identify_sorted_half(arr, low, high): """ Identifies which half of a rotated sorted array is sorted. Returns: 'left' if the left half [low..mid] is sorted 'right' if the right half [mid..high] is sorted 'both' if the entire range is sorted (no rotation in this range) """ if low >= high: return 'both' # Single element or empty mid = (low + high) // 2 # Check if left half is sorted left_sorted = arr[low] <= arr[mid] # Check if right half is sorted right_sorted = arr[mid] <= arr[high] if left_sorted and right_sorted: return 'both' # Entire range is sorted elif left_sorted: return 'left' else: return 'right' # Demonstrationdef visualize_sorted_half(arr): """Visualizes which half is sorted at each binary search step.""" low, high = 0, len(arr) - 1 step = 0 print(f"Array: {arr}") print("-" * 50) while low <= high: mid = (low + high) // 2 result = identify_sorted_half(arr, low, high) left_half = arr[low:mid+1] right_half = arr[mid:high+1] print(f"Step {step}:") print(f" Range: [{low}, {high}], mid = {mid}") print(f" Left half: {left_half} {'✓ SORTED' if result in ['left', 'both'] else ''}") print(f" Right half: {right_half} {'✓ SORTED' if result in ['right', 'both'] else ''}") print(f" arr[low]={arr[low]}, arr[mid]={arr[mid]}, arr[high]={arr[high]}") print() # For demonstration, just shrink range if result == 'left': high = mid - 1 else: low = mid + 1 step += 1 if step > 5: break # Test with different rotationsprint("=" * 60)print("Example 1: Rotation point in middle-right")visualize_sorted_half([4, 5, 6, 7, 1, 2, 3]) print("=" * 60)print("Example 2: Rotation point in middle-left")visualize_sorted_half([6, 7, 1, 2, 3, 4, 5]) print("=" * 60)print("Example 3: No rotation (fully sorted)")visualize_sorted_half([1, 2, 3, 4, 5, 6, 7])To truly internalize this concept, let's systematically analyze all possible rotation positions and see exactly which half ends up sorted. Understanding these patterns will make the algorithm feel intuitive rather than memorized.
| Rotation | Resulting Array | Pivot Index | arr[0] vs arr[3] | Sorted Half |
|---|---|---|---|---|
| k=0 | [1, 2, 3, 4, 5, 6, 7] | None | 1 ≤ 4 ✓ | Both (no rotation) |
| k=1 | [7, 1, 2, 3, 4, 5, 6] | 0 | 7 > 3 | Right: [3,4,5,6] |
| k=2 | [6, 7, 1, 2, 3, 4, 5] | 1 | 6 > 2 | Right: [2,3,4,5] |
| k=3 | [5, 6, 7, 1, 2, 3, 4] | 2 | 5 > 1 | Right: [1,2,3,4] |
| k=4 | [4, 5, 6, 7, 1, 2, 3] | 3 | 4 ≤ 7 ✓ | Left: [4,5,6,7] |
| k=5 | [3, 4, 5, 6, 7, 1, 2] | 4 | 3 ≤ 6 ✓ | Left: [3,4,5,6] |
| k=6 | [2, 3, 4, 5, 6, 7, 1] | 5 | 2 ≤ 5 ✓ | Left: [2,3,4,5] |
Pattern observation:
Looking at the table, notice that:
arr[0] > arr[mid]arr[0] ≤ arr[mid]This is precisely why our single comparison arr[low] ≤ arr[mid] works: it detects whether the rotation point has 'polluted' the left half.
Think of it this way: In a normal sorted array, the first element is always ≤ the middle element. If arr[low] > arr[mid], something is 'wrong' with the left half—it contains the pivot where values jump from high back to low. So the right half must be the 'clean' sorted portion.
Real interview code must handle edge cases flawlessly. Let's examine the boundary conditions that can trip up even experienced developers.
[5] — Both 'halves' are trivially sorted. Our check handles this correctly because low = mid = high.[2, 1] — mid = 0, so left 'half' is just [2]. Check: arr[0] ≤ arr[0]? Yes, so left is sorted. Correct![1, 2] — mid = 0, left half is [1]. Right half is [1, 2]. Check: arr[0] ≤ arr[0]? Yes. Both are valid.[3, 4, 5, 1, 2] — mid = 2 (value 5). arr[0]=3, arr[2]=5. Check: 3 ≤ 5? Yes. Left half [3,4,5] is sorted. Correct![5, 1, 2, 3, 4] — mid = 2 (value 2). arr[0]=5, arr[2]=2. Check: 5 ≤ 2? No. Right half [2,3,4] is sorted. Correct![1, 2, 3, 4, 5] — arr[0]=1, arr[2]=3. Check: 1 ≤ 3? Yes. Left half is sorted. (Right half is also sorted.)123456789101112131415161718192021222324252627282930313233343536373839404142
def test_sorted_half_identification(): """Comprehensive test cases for sorted half identification.""" test_cases = [ # (array, expected_sorted_half_at_first_iteration) ([5], "both"), # Single element ([2, 1], "left"), # Two elements, rotated ([1, 2], "both"), # Two elements, not rotated ([3, 4, 5, 1, 2], "left"), # Minimum at position after mid ([5, 1, 2, 3, 4], "right"), # Minimum at position 1 ([1, 2, 3, 4, 5], "both"), # Not rotated ([4, 5, 6, 7, 0, 1, 2], "left"), # Classic LeetCode example ([2, 1], "left"), # Wwo elements rotated once ([11, 13, 15, 17], "both"), # Not rotated, all ascending ([2, 3, 4, 5, 1], "left"), # Rotation at last position ] print("Testing Sorted Half Identification") print("=" * 60) for i, (arr, expected) in enumerate(test_cases): low, high = 0, len(arr) - 1 mid = (low + high) // 2 left_sorted = arr[low] <= arr[mid] right_sorted = arr[mid] <= arr[high] if left_sorted and right_sorted: result = "both" elif left_sorted: result = "left" else: result = "right" status = "✓ PASS" if result == expected else "✗ FAIL" print(f"Test {i+1}: {arr}") print(f" arr[{low}]={arr[low]}, arr[{mid}]={arr[mid]}, arr[{high}]={arr[high]}") print(f" Expected: {expected}, Got: {result} {status}") print() test_sorted_half_identification()When computing mid, use mid = low + (high - low) // 2 instead of (low + high) // 2 to prevent integer overflow in languages like Java and C++. Python handles arbitrary precision integers, but the habit is worth developing.
Understanding that one half is always sorted isn't just a cute observation—it's the key that unlocks binary search in rotated arrays. Here's why:
Binary search requires a decision criterion.
In standard binary search on a sorted array, the decision is simple:
target < arr[mid], search lefttarget > arr[mid], search rightThis works because we know which direction contains smaller/larger values.
In a rotated array, we lost that guarantee... almost.
We can't globally reason about which side has smaller or larger values. But we can reason about the sorted half:
This transforms the problem from "where should I look?" to "is my target in the portion I fully understand?"
In the next page, we'll build the complete search algorithm. The structure will be: (1) Find mid, (2) Identify which half is sorted, (3) Check if target is in the sorted half's range, (4) Eliminate the other half. This single insight enables that entire strategy.
The best way to internalize this concept is to build a strong visual and intuitive mental model. Here are several ways to think about rotated arrays:
Different people find different models intuitive. The mountain model works for visual thinkers. The two-runs model works for those who think mathematically. Choose the one that helps you 'see' why one half must be sorted, and the algorithm will feel natural rather than memorized.
We've established the fundamental insight that makes rotated array search possible. Let's consolidate what we've learned:
What's next:
Now that you can identify which half is sorted, the next page shows how to build the complete search algorithm. We'll use this insight to make definitive decisions about which half to search—transforming the rotated array problem from daunting to elegant.
You now understand the foundational insight for rotated array search: one half is always sorted, and a single O(1) check tells you which. This is the hardest part to truly internalize—the algorithm itself follows naturally from here. Next, we'll build the modified binary search strategy.