Identifying the Sorted Portion - Search in Rotated Arrays | OneNoughtOne

0/361

Data Structures & AlgorithmsSearch in Rotated Arrays

Search in Rotated Arrays

LevelIntermediate

Duration60 mins

TopicSearch in Rotated Arrays

1 / 4

Identifying the Sorted Portion

The Rotated Array Challenge

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.

What You Will Learn

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.

What Is a Rotated Sorted Array?

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:

Elements A[k], A[k+1], ..., A[n-1] appear first (in order)
Elements A[0], A[1], ..., A[k-1] appear after (in order)

The rotation "wraps around" the array, creating exactly two sorted subsequences.

Visualizing Array Rotation

Let's trace through several rotations of the same sorted array to build intuition.

Input

Original sorted array: [1, 2, 3, 4, 5, 6, 7]

Output

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 original

Explanation

Notice 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

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:

Circular buffers — Log systems often use circular buffers where the 'start' wraps around
Scheduling systems — Task queues that rotate based on priority or time
Database indexing — Some B-tree variants handle wrap-around ranges
Financial data — Rolling windows of time-series data that 'rotate' daily

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.

The Key Observation — One Half Is Always Sorted

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.

The Fundamental Invariant

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)

The left half [low..mid] contains only elements from the second sorted run
Since these elements were contiguous in the original sorted array, they remain sorted
Therefore: left half is sorted

Case 2: The rotation point p is in the left half (p ≤ mid)

The right half [mid..high] contains only elements from the first sorted run (post-rotation)
These elements were also contiguous in the original sorted array
Therefore: right half is sorted

Case 3: The array is not actually rotated (or rotated n times)

The entire array is sorted, meaning both halves are sorted

In all cases, at least one half is sorted. This is the invariant we exploit.

Converting Mermaid diagram...

How to Identify the Sorted Half

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:

Sorted Half Detection Rules

•If arr[low] ≤ arr[mid]: The LEFT half [low..mid] is sorted. This is because in a sorted sequence, the first element must be ≤ the middle element.
•If arr[low] > arr[mid]: The RIGHT half [mid..high] is sorted. The left half contains the rotation point, so the right half must be the clean sorted portion.

Why arr[low] ≤ arr[mid], Not arr[low] < arr[mid]?

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:

Check: Is arr[0] ≤ arr[3]? Is 4 ≤ 7? Yes
Therefore: Left half [4, 5, 6, 7] is sorted
This tells us: If our target is ≥ 4 AND ≤ 7, search left; otherwise search right

Now consider arr = [5, 6, 7, 1, 2, 3, 4] with low = 0, high = 6, mid = 3:

Check: Is arr[0] ≤ arr[3]? Is 5 ≤ 1? No
Therefore: Right half [1, 2, 3, 4] is sorted
This tells us: If our target is ≥ 1 AND ≤ 4, search right; otherwise search left

identify_sorted_half.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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'
 
 
# Demonstration
def 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 rotations
print("=" * 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])

Visual Analysis of Rotation Scenarios

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 Scenarios for Array [1, 2, 3, 4, 5, 6, 7]
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:

When the pivot is in indices 0-2 (left half): The right half is sorted, and arr[0] > arr[mid]
When the pivot is in indices 3-5 (right half): The left half is sorted, and arr[0] ≤ arr[mid]
When there's no pivot (k=0): Both conditions pass, both halves are sorted

This is precisely why our single comparison arr[low] ≤ arr[mid] works: it detects whether the rotation point has 'polluted' the left half.

Intuitive Way to Remember

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.

Edge Cases in Sorted Half Identification

Real interview code must handle edge cases flawlessly. Let's examine the boundary conditions that can trip up even experienced developers.

Critical Edge Cases

•Single element array: [5] — Both 'halves' are trivially sorted. Our check handles this correctly because low = mid = high.
•Two element array: [2, 1] — mid = 0, so left 'half' is just [2]. Check: arr[0] ≤ arr[0]? Yes, so left is sorted. Correct!
•Two element array (not rotated): [1, 2] — mid = 0, left half is [1]. Right half is [1, 2]. Check: arr[0] ≤ arr[0]? Yes. Both are valid.
•Minimum is at mid: [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!
•Maximum is at mid: [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!
•No rotation (fully sorted): [1, 2, 3, 4, 5] — arr[0]=1, arr[2]=3. Check: 1 ≤ 3? Yes. Left half is sorted. (Right half is also sorted.)

edge_cases_test.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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()

Common Mistake: Off-by-One in Mid Calculation

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.

The Strategic Value of This Insight

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:

If target < arr[mid], search left
If target > arr[mid], search right

This 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:

If the sorted half is [4, 5, 6, 7], we know exactly what values are there
We can check: is our target in the range [4, 7]?
If yes, search that half. If no, search the other.

This transforms the problem from "where should I look?" to "is my target in the portion I fully understand?"

Without This Insight

•Array is partially sorted, can't use binary search
•Would need to find pivot first (extra O(log n))
•Or resort to linear search O(n)
•No clear decision at each step
•Algorithm feels like guesswork

With This Insight

•At each step, one half is guaranteed sorted
•Can make definitive decisions about sorted half
•Single pass O(log n) is possible
•Clear, systematic algorithm
•Elegant extension of binary search

Preview of the Algorithm

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.

Building Your Mental Model

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:

Mental Models for Rotated Arrays

•The Mountain Range Model: Imagine a sorted array as a mountain that rises from left to right. Rotation creates a 'cliff' where the mountain suddenly drops. When you look at any section, one side of the cliff is a smooth upward slope (sorted), and the other crosses the cliff (broken).
•The Clock Model: Think of the array wrapped around a circular clock. The values increase as you go clockwise. Rotation just changes which position is '12 o'clock'. Any arc of less than 180° covers either the continuous increasing portion or crosses the 12 o'clock mark (the minimum).
•The Cut Deck Model: A sorted array is a sorted deck of cards. Rotation is cutting the deck—taking the bottom portion and placing it on top. When you look at half the deck, either you see a continuous run from the original deck, or you see cards from both the top and bottom portions.
•The Two Runs Model: A rotated array is simply two sorted runs concatenated: [large values in order] + [small values in order]. When you split at mid, one half contains only one run (sorted), and the other half might contain parts of both runs (broken).

Whichever Model Clicks, Use It

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.

Summary: The Foundation for Rotated Array Search

We've established the fundamental insight that makes rotated array search possible. Let's consolidate what we've learned:

Key Takeaways

•A rotated sorted array has exactly two sorted runs — the elements 'before' and 'after' the rotation point.
•When divided at mid, one half is always fully sorted — because the rotation point can only be in one half.
•The check is simple: arr[low] ≤ arr[mid] means left is sorted — otherwise, right is sorted.
•This single comparison takes O(1) time — adding no overhead to binary search.
•This insight enables binary search in rotated arrays — by giving us a portion we can reason about definitively.
•Edge cases are handled naturally — single elements, two elements, and unrotated arrays all work correctly.

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.

Page Complete

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.