Rotated Arrays - Learning Module

Loading content...

0/276

Modified Binary Search Strategy

From Insight to Algorithm

With the foundational insight in hand—that one half of a rotated sorted array is always sorted—we can now construct a precise, elegant algorithm for searching. This isn't a hack or workaround; it's a principled extension of binary search that maintains O(log n) time complexity.

The strategy is beautifully simple:

Find the middle element
Determine which half is sorted
Check if the target falls within the sorted half's range
If yes, search that half. If no, search the other half.

This guarantees that we eliminate exactly half the search space with each comparison—the hallmark of logarithmic efficiency.

What You Will Learn

By the end of this page, you will be able to implement a complete binary search algorithm for rotated sorted arrays. You'll understand every decision branch, handle all edge cases, and implement both iterative and recursive versions with confidence.

The Algorithm Framework

Let's establish the complete algorithm structure before diving into implementation. The key is understanding the decision tree at each step.

At each iteration, we must answer two questions:

Which half is sorted? — Answered by comparing arr[low] with arr[mid]
Is the target in the sorted half? — Answered by checking if target is within that half's range

Depending on the answers, we set low and high to search the appropriate half.

The Four Cases

•Case 1: Left half sorted AND target in left half — Set high = mid - 1 (search left)
•Case 2: Left half sorted AND target NOT in left half — Set low = mid + 1 (search right)
•Case 3: Right half sorted AND target in right half — Set low = mid + 1 (search right)
•Case 4: Right half sorted AND target NOT in right half — Set high = mid - 1 (search left)

Converting Mermaid diagram...

The Range Check Is Critical

When checking if target is in a range, be precise about boundaries. For the left half [low..mid], check arr[low] <= target < arr[mid] (not including mid, since we already checked it). For the right half, check arr[mid] < target <= arr[high].

Iterative Implementation — The Standard Approach

The iterative version is preferred in interviews and production code because it avoids recursion overhead and stack limitations. Let's build it step by step with comprehensive comments explaining every decision.

search_rotated_array.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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
def search_rotated(nums: list[int], target: int) -> int:
    """
    Search for target in a rotated sorted array with distinct values.
    
    Args:
        nums: A rotated sorted array of distinct integers
        target: The value to search for
        
    Returns:
        The index of target if found, -1 otherwise
        
    Time Complexity: O(log n) - standard binary search
    Space Complexity: O(1) - only using a few variables
    
    Key Insight: At each step, one half is always sorted, allowing
    us to make definitive decisions about which half to search.
    """
    if not nums:
        return -1
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        # Prevent potential overflow in other languages
        mid = low + (high - low) // 2
        
        # Found the target!
        if nums[mid] == target:
            return mid
        
        # Determine which half is sorted
        # Key check: if nums[low] <= nums[mid], left half is sorted
        
        if nums[low] <= nums[mid]:
            # LEFT HALF IS SORTED: [low..mid] contains sequential values
            # We know exactly what values are in this range: nums[low] to nums[mid]
            
            # Check if target is within the sorted left half
            if nums[low] <= target < nums[mid]:
                # Target is in the sorted left half
                # We can safely eliminate the right half
                high = mid - 1
            else:
                # Target is NOT in the left half
                # It must be in the right half (if it exists at all)
                low = mid + 1
        else:
            # RIGHT HALF IS SORTED: [mid..high] contains sequential values
            # We know exactly what values are in this range: nums[mid] to nums[high]
            
            # Check if target is within the sorted right half
            if nums[mid] < target <= nums[high]:
                # Target is in the sorted right half
                # We can safely eliminate the left half
                low = mid + 1
            else:
                # Target is NOT in the right half
                # It must be in the left half (if it exists at all)
                high = mid - 1
    
    # If we exit the loop, target was not found
    return -1
 
 
def search_with_trace(nums: list[int], target: int) -> int:
    """Same algorithm with detailed tracing for learning."""
    if not nums:
        return -1
    
    low, high = 0, len(nums) - 1
    iteration = 0
    
    print(f"Searching for {target} in {nums}")
    print("=" * 60)
    
    while low <= high:
        mid = low + (high - low) // 2
        iteration += 1
        
        print(f"\nIteration {iteration}:")
        print(f"  Range: [{low}, {high}], mid = {mid}")
        print(f"  arr[low]={nums[low]}, arr[mid]={nums[mid]}, arr[high]={nums[high]}")
        
        if nums[mid] == target:
            print(f"  ✓ FOUND! nums[{mid}] = {target}")
            return mid
        
        if nums[low] <= nums[mid]:
            print(f"  Left half [{nums[low]}...{nums[mid]}] is SORTED")
            
            if nums[low] <= target < nums[mid]:
                print(f"  {target} is in sorted left half [{nums[low]}, {nums[mid]})")
                print(f"  → Move high to {mid - 1}")
                high = mid - 1
            else:
                print(f"  {target} is NOT in sorted left half")
                print(f"  → Move low to {mid + 1}")
                low = mid + 1
        else:
            print(f"  Right half [{nums[mid]}...{nums[high]}] is SORTED")
            
            if nums[mid] < target <= nums[high]:
                print(f"  {target} is in sorted right half ({nums[mid]}, {nums[high]}]")
                print(f"  → Move low to {mid + 1}")
                low = mid + 1
            else:
                print(f"  {target} is NOT in sorted right half")
                print(f"  → Move high to {mid - 1}")
                high = mid - 1
    
    print(f"\n✗ NOT FOUND after {iteration} iterations")
    return -1
 
 
# Demonstration
if __name__ == "__main__":
    # Test case 1: Target in the larger sorted portion
    print("\n" + "=" * 60)
    print("TEST 1: Target in the larger sorted portion")
    print("=" * 60)
    search_with_trace([4, 5, 6, 7, 0, 1, 2], 6)
    
    # Test case 2: Target in the smaller sorted portion
    print("\n" + "=" * 60)
    print("TEST 2: Target in the smaller sorted portion")
    print("=" * 60)
    search_with_trace([4, 5, 6, 7, 0, 1, 2], 1)
    
    # Test case 3: Target not in array
    print("\n" + "=" * 60)
    print("TEST 3: Target not in array")
    print("=" * 60)
    search_with_trace([4, 5, 6, 7, 0, 1, 2], 3)
    
    # Test case 4: Target at rotation point
    print("\n" + "=" * 60)
    print("TEST 4: Target at rotation point (minimum)")
    print("=" * 60)
    search_with_trace([4, 5, 6, 7, 0, 1, 2], 0)

Recursive Implementation — For Completeness

While the iterative version is generally preferred, understanding the recursive formulation helps solidify the divide-and-conquer nature of the algorithm. It also makes the logic flow more apparent for some learners.

Key insight for recursion: Each recursive call reduces the problem to searching in exactly one half, maintaining the O(log n) guarantee.

search_rotated_recursive.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
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
75
76
77
78
79
80
81
82
83
84
def search_rotated_recursive(nums: list[int], target: int) -> int:
    """
    Recursive implementation of search in rotated sorted array.
    
    Time Complexity: O(log n)
    Space Complexity: O(log n) due to recursion stack
    """
    
    def search(low: int, high: int) -> int:
        # Base case: empty range
        if low > high:
            return -1
        
        mid = low + (high - low) // 2
        
        # Base case: found the target
        if nums[mid] == target:
            return mid
        
        # Recursive case: determine which half to search
        if nums[low] <= nums[mid]:
            # Left half is sorted
            if nums[low] <= target < nums[mid]:
                # Target is in sorted left half
                return search(low, mid - 1)
            else:
                # Target is in unsorted right half
                return search(mid + 1, high)
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[high]:
                # Target is in sorted right half
                return search(mid + 1, high)
            else:
                # Target is in unsorted left half
                return search(low, mid - 1)
    
    if not nums:
        return -1
    
    return search(0, len(nums) - 1)
 
 
# Tail-recursive variant (can be optimized by compilers in some languages)
def search_tail_recursive(nums: list[int], target: int,
                          low: int = None, high: int = None) -> int:
    """
    Tail-recursive variant where recursive call is the last operation.
    Some languages/compilers can optimize this to iteration.
    """
    if low is None:
        low = 0
    if high is None:
        high = len(nums) - 1 if nums else -1
    
    # Base case: empty range
    if low > high:
        return -1
    
    mid = low + (high - low) // 2
    
    # Base case: found
    if nums[mid] == target:
        return mid
    
    # Tail recursive calls
    if nums[low] <= nums[mid]:
        if nums[low] <= target < nums[mid]:
            return search_tail_recursive(nums, target, low, mid - 1)
        else:
            return search_tail_recursive(nums, target, mid + 1, high)
    else:
        if nums[mid] < target <= nums[high]:
            return search_tail_recursive(nums, target, mid + 1, high)
        else:
            return search_tail_recursive(nums, target, low, mid - 1)
 
 
# Test
arr = [4, 5, 6, 7, 0, 1, 2]
print(f"Array: {arr}")
print(f"search_rotated_recursive(arr, 5) = {search_rotated_recursive(arr, 5)}")  # 1
print(f"search_rotated_recursive(arr, 0) = {search_rotated_recursive(arr, 0)}")  # 4
print(f"search_rotated_recursive(arr, 3) = {search_rotated_recursive(arr, 3)}")  # -1

Iteration vs Recursion Trade-offs

The iterative version uses O(1) space, while recursion uses O(log n) stack space. In most interviews and production systems, the iterative version is preferred. However, understanding the recursive version helps when dealing with variations or when the problem naturally fits a recursive structure.

Deep Dive into the Decision Logic

Let's examine each decision branch in detail to understand why it's correct. This level of analysis is what separates engineers who 'know' an algorithm from those who understand it.

Branch 1: Left half is sorted (nums[low] <= nums[mid])

When this condition is true, we know that [nums[low], nums[low+1], ..., nums[mid]] are in ascending order. This gives us precise knowledge:

The minimum value in the left half is nums[low]
The maximum value in the left half is nums[mid]
Any value x is in the left half if and only if nums[low] <= x <= nums[mid]

However, we've already checked if nums[mid] == target, so we use nums[low] <= target < nums[mid] (strict inequality on the right).

Decision Logic for Left-Sorted Case
Condition	What It Tells Us	Action
nums[low] <= target	Target is ≥ minimum of left half	Possibly in left
target < nums[mid]	Target is < maximum of left half	Definitely in left
Both true	Target must be in [low, mid-1]	high = mid - 1
Either false	Target cannot be in left half	low = mid + 1

Branch 2: Right half is sorted (nums[low] > nums[mid])

When the left half is not sorted (contains the rotation point), the right half must be sorted. We now have precise knowledge about the right half:

The minimum value in the right half is nums[mid] (or nums[mid+1] after we've checked mid)
The maximum value in the right half is nums[high]
Any value x is in the right half if and only if nums[mid] < x <= nums[high]

Again, we use strict inequality on the left since we've already checked mid.

Decision Logic for Right-Sorted Case
Condition	What It Tells Us	Action
nums[mid] < target	Target is > the mid value	Possibly in right
target <= nums[high]	Target is ≤ maximum of right half	Definitely in right
Both true	Target must be in [mid+1, high]	low = mid + 1
Either false	Target cannot be in right half	high = mid - 1

The Key Principle

We only make definitive statements about the SORTED half. We never try to reason about what's in the unsorted half—we only conclude that if the target isn't in the sorted half, it must be in the other (if anywhere). This is why the algorithm is robust.

Worked Examples — Trace Through Step by Step

The best way to internalize this algorithm is to trace through examples by hand. Let's work through several scenarios.

Example 1: Target in the higher portion

Array: [4, 5, 6, 7, 0, 1, 2], Target: 5

Searching for 5 in [4, 5, 6, 7, 0, 1, 2]Target is in the left (higher values) portion.

Input

nums = [4, 5, 6, 7, 0, 1, 2], target = 5

Output

Iteration 1:
  low=0, high=6, mid=3
  nums[0]=4, nums[3]=7, nums[6]=2
  Check: nums[0] ≤ nums[3]? 4 ≤ 7? YES → Left half sorted
  Check: 4 ≤ 5 < 7? YES → Target is in sorted left half
  Action: high = mid - 1 = 2

Iteration 2:
  low=0, high=2, mid=1
  nums[0]=4, nums[1]=5, nums[2]=6
  Check: nums[mid] == target? 5 == 5? YES!
  
Result: Found at index 1 ✓

Explanation

Only 2 iterations needed for an array of 7 elements — O(log n) in action.

Example 2: Target in the lower portion

Array: [4, 5, 6, 7, 0, 1, 2], Target: 1

Searching for 1 in [4, 5, 6, 7, 0, 1, 2]Target is in the right (lower values) portion.

Input

nums = [4, 5, 6, 7, 0, 1, 2], target = 1

Output

Iteration 1:
  low=0, high=6, mid=3
  nums[0]=4, nums[3]=7, nums[6]=2
  Check: nums[0] ≤ nums[3]? 4 ≤ 7? YES → Left half sorted
  Check: 4 ≤ 1 < 7? NO (1 < 4) → Target NOT in sorted left half
  Action: low = mid + 1 = 4

Iteration 2:
  low=4, high=6, mid=5
  nums[4]=0, nums[5]=1, nums[6]=2
  Check: nums[mid] == target? 1 == 1? YES!
  
Result: Found at index 5 ✓

Explanation

The algorithm correctly recognizes that 1 is not in [4,5,6,7] and searches the right half.

Example 3: Target not present

Array: [4, 5, 6, 7, 0, 1, 2], Target: 3

Searching for 3 in [4, 5, 6, 7, 0, 1, 2]Target does not exist in the array.

Input

nums = [4, 5, 6, 7, 0, 1, 2], target = 3

Output

Iteration 1:
  low=0, high=6, mid=3
  Left half [4,5,6,7] sorted
  3 not in [4,7] → low = 4

Iteration 2:
  low=4, high=6, mid=5
  nums[4]=0 ≤ nums[5]=1? YES → Left half sorted
  0 ≤ 3 < 1? NO (3 > 1) → low = 6
  
Iteration 3:
  low=6, high=6, mid=6
  nums[mid]=2 ≠ 3
  nums[6]=2 ≤ nums[6]=2? YES → Left half sorted
  2 ≤ 3 < 2? NO → low = 7
  
low > high → Exit loop
Result: Not found, return -1

Explanation

After 3 iterations, the search space is exhausted. The algorithm correctly returns -1.

Common Mistakes and How to Avoid Them

This algorithm has several subtle pitfalls that trip up even experienced developers. Understanding these common mistakes will help you implement it correctly under interview pressure.

Common Mistakes

•Mistake 1: Using < instead of <= in nums[low] <= nums[mid] When low == mid (subarray of size 1-2), using strict < fails. The single element is both the left half and trivially sorted. Use <= to handle this correctly.
•Mistake 2: Off-by-one in range checks For left half: use nums[low] <= target < nums[mid] (exclude mid, we already checked it). For right half: use nums[mid] < target <= nums[high] (exclude mid, we already checked it). Getting these boundaries wrong causes infinite loops or missed elements.
•Mistake 3: Integer overflow in mid calculation In Java/C++, (low + high) / 2 can overflow. Always use low + (high - low) / 2. Python handles big integers automatically, but the habit is worth developing.
•Mistake 4: Forgetting to check if nums[mid] == target first Always check for the target at mid before deciding which half to search. Missing this causes you to skip the target when it's exactly at mid.
•Mistake 5: Wrong loop condition Use while (low <= high), not while (low < high). The condition low == high represents a subarray with exactly one element that must be checked.

wrong_approach.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# ❌ WRONG: Common mistakes combined
 
def search_buggy(nums, target):
    low, high = 0, len(nums) - 1
    
    # Bug 1: low < high misses last element
    while low < high:
        # Bug 2: Potential overflow in other langs
        mid = (low + high) // 2
        
        # Bug 3: Using < instead of <=
        if nums[low] < nums[mid]:
            # Bug 4: Wrong range bounds
            if nums[low] <= target <= nums[mid]:
                high = mid  # Bug 5: Should be mid-1
            else:
                low = mid  # Bug 6: Should be mid+1
        # ... more bugs likely
 
# This will fail on many cases!

correct_approach.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
# ✅ CORRECT: All pitfalls avoided
 
def search_correct(nums, target):
    low, high = 0, len(nums) - 1
    
    # Correct: <= to check single element
    while low <= high:
        # Correct: Overflow-safe
        mid = low + (high - low) // 2
        
        # Correct: Check target first
        if nums[mid] == target:
            return mid
        
        # Correct: <= handles low==mid
        if nums[low] <= nums[mid]:
            # Correct: Exclude mid with <
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        # ... symmetrical for right half
 
# This handles all edge cases!

Verification and Testing Strategy

In an interview, you should briefly mention how you'd verify your solution. A systematic testing strategy demonstrates engineering maturity.

Categories of test cases:

Essential Test Cases

•Empty array: Should return -1
•Single element — target present: Should return 0
•Single element — target absent: Should return -1
•Two elements — various rotations: Test [1,2], [2,1] with target in each position
•No rotation (fully sorted): Ensures algorithm works on edge case
•Target at start: First element is the target
•Target at end: Last element is the target
•Target at rotation point: Minimum element is the target
•Target at maximum (before rotation point): Maximum element is the target
•Target in left portion: Higher values, left of rotation point
•Target in right portion: Lower values, right of rotation point
•Target not present — would be in left portion:
•Target not present — would be in right portion:
•Target not present — smaller than minimum:
•Target not present — larger than maximum:

test_rotated_search.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
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
75
76
77
78
def run_comprehensive_tests(search_fn):
    """Test suite for rotated array search."""
    
    test_cases = [
        # (array, target, expected_index, description)
        ([], 1, -1, "Empty array"),
        ([5], 5, 0, "Single element - present"),
        ([5], 3, -1, "Single element - absent"),
        ([1, 2], 1, 0, "Two elements sorted - first"),
        ([1, 2], 2, 1, "Two elements sorted - second"),
        ([2, 1], 2, 0, "Two elements rotated - first"),
        ([2, 1], 1, 1, "Two elements rotated - second"),
        ([2, 1], 3, -1, "Two elements rotated - absent"),
        ([1, 2, 3, 4, 5], 3, 2, "Not rotated - middle"),
        ([4, 5, 6, 7, 0, 1, 2], 4, 0, "Target at start"),
        ([4, 5, 6, 7, 0, 1, 2], 2, 6, "Target at end"),
        ([4, 5, 6, 7, 0, 1, 2], 0, 4, "Target at rotation point (min)"),
        ([4, 5, 6, 7, 0, 1, 2], 7, 3, "Target at max (before rotation)"),
        ([4, 5, 6, 7, 0, 1, 2], 5, 1, "Target in left portion"),
        ([4, 5, 6, 7, 0, 1, 2], 1, 5, "Target in right portion"),
        ([4, 5, 6, 7, 0, 1, 2], 3, -1, "Absent - would be in right"),
        ([4, 5, 6, 7, 0, 1, 2], 8, -1, "Absent - larger than max"),
        ([4, 5, 6, 7, 0, 1, 2], -1, -1, "Absent - smaller than min"),
        ([5, 1, 2, 3, 4], 1, 1, "Rotation near start"),
        ([2, 3, 4, 5, 1], 1, 4, "Rotation near end"),
    ]
    
    print("Running Comprehensive Test Suite")
    print("=" * 70)
    
    passed = 0
    failed = 0
    
    for arr, target, expected, desc in test_cases:
        result = search_fn(arr, target)
        status = "✓" if result == expected else "✗"
        
        if result == expected:
            passed += 1
        else:
            failed += 1
            print(f"{status} FAIL: {desc}")
            print(f"    Array: {arr}, Target: {target}")
            print(f"    Expected: {expected}, Got: {result}")
    
    print(f"\nResults: {passed} passed, {failed} failed")
    return failed == 0
 
 
# Run tests
from typing import List
 
def search(nums: List[int], target: int) -> int:
    if not nums:
        return -1
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if nums[mid] == target:
            return mid
        
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    
    return -1
 
run_comprehensive_tests(search)

Summary: The Complete Strategy

We've built a complete, production-ready algorithm for searching in rotated sorted arrays. Let's consolidate the key points:

Key Takeaways

•The algorithm is standard binary search with one twist: Before searching a half, determine which half is sorted.
•Use nums[low] <= nums[mid] to detect if left half is sorted. This handles all edge cases including single elements.
•For the sorted half, check if target is in its range. If yes, search there. If no, search the other half.
•Always check nums[mid] == target first before deciding which direction to go.
•Use low <= high as the loop condition to handle single-element subarrays.
•Use low + (high - low) // 2 for mid calculation to prevent overflow.
•Time complexity remains O(log n) — we still eliminate half the search space each iteration.
•Space complexity is O(1) for iterative, O(log n) for recursive.

What's next:

This algorithm assumes distinct elements. But what happens when the array contains duplicates? The problem becomes significantly more complex, as duplicates can violate our key invariant. The next page covers the strategies and trade-offs for handling duplicates in rotated arrays.

Page Complete

You now have a complete, tested implementation of binary search for rotated sorted arrays with distinct elements. This is a high-frequency interview question, and you're equipped to solve it correctly under pressure. Next, we tackle the challenging extension: what happens when duplicates are present?

Modified Binary Search Strategy

From Insight to Algorithm

The strategy is beautifully simple:

Find the middle element
Determine which half is sorted
Check if the target falls within the sorted half's range
If yes, search that half. If no, search the other half.

This guarantees that we eliminate exactly half the search space with each comparison—the hallmark of logarithmic efficiency.

What You Will Learn

The Algorithm Framework

Let's establish the complete algorithm structure before diving into implementation. The key is understanding the decision tree at each step.

At each iteration, we must answer two questions:

Which half is sorted? — Answered by comparing arr[low] with arr[mid]
Is the target in the sorted half? — Answered by checking if target is within that half's range

Depending on the answers, we set low and high to search the appropriate half.

The Four Cases

•Case 1: Left half sorted AND target in left half — Set high = mid - 1 (search left)
•Case 2: Left half sorted AND target NOT in left half — Set low = mid + 1 (search right)
•Case 3: Right half sorted AND target in right half — Set low = mid + 1 (search right)
•Case 4: Right half sorted AND target NOT in right half — Set high = mid - 1 (search left)

Converting Mermaid diagram...

The Range Check Is Critical

Iterative Implementation — The Standard Approach

search_rotated_array.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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
def search_rotated(nums: list[int], target: int) -> int:
    """
    Search for target in a rotated sorted array with distinct values.
    
    Args:
        nums: A rotated sorted array of distinct integers
        target: The value to search for
        
    Returns:
        The index of target if found, -1 otherwise
        
    Time Complexity: O(log n) - standard binary search
    Space Complexity: O(1) - only using a few variables
    
    Key Insight: At each step, one half is always sorted, allowing
    us to make definitive decisions about which half to search.
    """
    if not nums:
        return -1
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        # Prevent potential overflow in other languages
        mid = low + (high - low) // 2
        
        # Found the target!
        if nums[mid] == target:
            return mid
        
        # Determine which half is sorted
        # Key check: if nums[low] <= nums[mid], left half is sorted
        
        if nums[low] <= nums[mid]:
            # LEFT HALF IS SORTED: [low..mid] contains sequential values
            # We know exactly what values are in this range: nums[low] to nums[mid]
            
            # Check if target is within the sorted left half
            if nums[low] <= target < nums[mid]:
                # Target is in the sorted left half
                # We can safely eliminate the right half
                high = mid - 1
            else:
                # Target is NOT in the left half
                # It must be in the right half (if it exists at all)
                low = mid + 1
        else:
            # RIGHT HALF IS SORTED: [mid..high] contains sequential values
            # We know exactly what values are in this range: nums[mid] to nums[high]
            
            # Check if target is within the sorted right half
            if nums[mid] < target <= nums[high]:
                # Target is in the sorted right half
                # We can safely eliminate the left half
                low = mid + 1
            else:
                # Target is NOT in the right half
                # It must be in the left half (if it exists at all)
                high = mid - 1
    
    # If we exit the loop, target was not found
    return -1
 
 
def search_with_trace(nums: list[int], target: int) -> int:
    """Same algorithm with detailed tracing for learning."""
    if not nums:
        return -1
    
    low, high = 0, len(nums) - 1
    iteration = 0
    
    print(f"Searching for {target} in {nums}")
    print("=" * 60)
    
    while low <= high:
        mid = low + (high - low) // 2
        iteration += 1
        
        print(f"\nIteration {iteration}:")
        print(f"  Range: [{low}, {high}], mid = {mid}")
        print(f"  arr[low]={nums[low]}, arr[mid]={nums[mid]}, arr[high]={nums[high]}")
        
        if nums[mid] == target:
            print(f"  ✓ FOUND! nums[{mid}] = {target}")
            return mid
        
        if nums[low] <= nums[mid]:
            print(f"  Left half [{nums[low]}...{nums[mid]}] is SORTED")
            
            if nums[low] <= target < nums[mid]:
                print(f"  {target} is in sorted left half [{nums[low]}, {nums[mid]})")
                print(f"  → Move high to {mid - 1}")
                high = mid - 1
            else:
                print(f"  {target} is NOT in sorted left half")
                print(f"  → Move low to {mid + 1}")
                low = mid + 1
        else:
            print(f"  Right half [{nums[mid]}...{nums[high]}] is SORTED")
            
            if nums[mid] < target <= nums[high]:
                print(f"  {target} is in sorted right half ({nums[mid]}, {nums[high]}]")
                print(f"  → Move low to {mid + 1}")
                low = mid + 1
            else:
                print(f"  {target} is NOT in sorted right half")
                print(f"  → Move high to {mid - 1}")
                high = mid - 1
    
    print(f"\n✗ NOT FOUND after {iteration} iterations")
    return -1
 
 
# Demonstration
if __name__ == "__main__":
    # Test case 1: Target in the larger sorted portion
    print("\n" + "=" * 60)
    print("TEST 1: Target in the larger sorted portion")
    print("=" * 60)
    search_with_trace([4, 5, 6, 7, 0, 1, 2], 6)
    
    # Test case 2: Target in the smaller sorted portion
    print("\n" + "=" * 60)
    print("TEST 2: Target in the smaller sorted portion")
    print("=" * 60)
    search_with_trace([4, 5, 6, 7, 0, 1, 2], 1)
    
    # Test case 3: Target not in array
    print("\n" + "=" * 60)
    print("TEST 3: Target not in array")
    print("=" * 60)
    search_with_trace([4, 5, 6, 7, 0, 1, 2], 3)
    
    # Test case 4: Target at rotation point
    print("\n" + "=" * 60)
    print("TEST 4: Target at rotation point (minimum)")
    print("=" * 60)
    search_with_trace([4, 5, 6, 7, 0, 1, 2], 0)

Recursive Implementation — For Completeness

Key insight for recursion: Each recursive call reduces the problem to searching in exactly one half, maintaining the O(log n) guarantee.

search_rotated_recursive.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
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
75
76
77
78
79
80
81
82
83
84
def search_rotated_recursive(nums: list[int], target: int) -> int:
    """
    Recursive implementation of search in rotated sorted array.
    
    Time Complexity: O(log n)
    Space Complexity: O(log n) due to recursion stack
    """
    
    def search(low: int, high: int) -> int:
        # Base case: empty range
        if low > high:
            return -1
        
        mid = low + (high - low) // 2
        
        # Base case: found the target
        if nums[mid] == target:
            return mid
        
        # Recursive case: determine which half to search
        if nums[low] <= nums[mid]:
            # Left half is sorted
            if nums[low] <= target < nums[mid]:
                # Target is in sorted left half
                return search(low, mid - 1)
            else:
                # Target is in unsorted right half
                return search(mid + 1, high)
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[high]:
                # Target is in sorted right half
                return search(mid + 1, high)
            else:
                # Target is in unsorted left half
                return search(low, mid - 1)
    
    if not nums:
        return -1
    
    return search(0, len(nums) - 1)
 
 
# Tail-recursive variant (can be optimized by compilers in some languages)
def search_tail_recursive(nums: list[int], target: int,
                          low: int = None, high: int = None) -> int:
    """
    Tail-recursive variant where recursive call is the last operation.
    Some languages/compilers can optimize this to iteration.
    """
    if low is None:
        low = 0
    if high is None:
        high = len(nums) - 1 if nums else -1
    
    # Base case: empty range
    if low > high:
        return -1
    
    mid = low + (high - low) // 2
    
    # Base case: found
    if nums[mid] == target:
        return mid
    
    # Tail recursive calls
    if nums[low] <= nums[mid]:
        if nums[low] <= target < nums[mid]:
            return search_tail_recursive(nums, target, low, mid - 1)
        else:
            return search_tail_recursive(nums, target, mid + 1, high)
    else:
        if nums[mid] < target <= nums[high]:
            return search_tail_recursive(nums, target, mid + 1, high)
        else:
            return search_tail_recursive(nums, target, low, mid - 1)
 
 
# Test
arr = [4, 5, 6, 7, 0, 1, 2]
print(f"Array: {arr}")
print(f"search_rotated_recursive(arr, 5) = {search_rotated_recursive(arr, 5)}")  # 1
print(f"search_rotated_recursive(arr, 0) = {search_rotated_recursive(arr, 0)}")  # 4
print(f"search_rotated_recursive(arr, 3) = {search_rotated_recursive(arr, 3)}")  # -1

Iteration vs Recursion Trade-offs

Deep Dive into the Decision Logic

Let's examine each decision branch in detail to understand why it's correct. This level of analysis is what separates engineers who 'know' an algorithm from those who understand it.

Branch 1: Left half is sorted (nums[low] <= nums[mid])

When this condition is true, we know that [nums[low], nums[low+1], ..., nums[mid]] are in ascending order. This gives us precise knowledge:

The minimum value in the left half is nums[low]
The maximum value in the left half is nums[mid]
Any value x is in the left half if and only if nums[low] <= x <= nums[mid]

However, we've already checked if nums[mid] == target, so we use nums[low] <= target < nums[mid] (strict inequality on the right).

Decision Logic for Left-Sorted Case
Condition	What It Tells Us	Action
nums[low] <= target	Target is ≥ minimum of left half	Possibly in left
target < nums[mid]	Target is < maximum of left half	Definitely in left
Both true	Target must be in [low, mid-1]	high = mid - 1
Either false	Target cannot be in left half	low = mid + 1

Branch 2: Right half is sorted (nums[low] > nums[mid])

When the left half is not sorted (contains the rotation point), the right half must be sorted. We now have precise knowledge about the right half:

The minimum value in the right half is nums[mid] (or nums[mid+1] after we've checked mid)
The maximum value in the right half is nums[high]
Any value x is in the right half if and only if nums[mid] < x <= nums[high]

Again, we use strict inequality on the left since we've already checked mid.

Decision Logic for Right-Sorted Case
Condition	What It Tells Us	Action
nums[mid] < target	Target is > the mid value	Possibly in right
target <= nums[high]	Target is ≤ maximum of right half	Definitely in right
Both true	Target must be in [mid+1, high]	low = mid + 1
Either false	Target cannot be in right half	high = mid - 1

The Key Principle

Worked Examples — Trace Through Step by Step

The best way to internalize this algorithm is to trace through examples by hand. Let's work through several scenarios.

Example 1: Target in the higher portion

Array: [4, 5, 6, 7, 0, 1, 2], Target: 5

Searching for 5 in [4, 5, 6, 7, 0, 1, 2]Target is in the left (higher values) portion.

Input

nums = [4, 5, 6, 7, 0, 1, 2], target = 5

Output

Iteration 1:
  low=0, high=6, mid=3
  nums[0]=4, nums[3]=7, nums[6]=2
  Check: nums[0] ≤ nums[3]? 4 ≤ 7? YES → Left half sorted
  Check: 4 ≤ 5 < 7? YES → Target is in sorted left half
  Action: high = mid - 1 = 2

Iteration 2:
  low=0, high=2, mid=1
  nums[0]=4, nums[1]=5, nums[2]=6
  Check: nums[mid] == target? 5 == 5? YES!
  
Result: Found at index 1 ✓

Explanation

Only 2 iterations needed for an array of 7 elements — O(log n) in action.

Example 2: Target in the lower portion

Array: [4, 5, 6, 7, 0, 1, 2], Target: 1

Searching for 1 in [4, 5, 6, 7, 0, 1, 2]Target is in the right (lower values) portion.

Input

nums = [4, 5, 6, 7, 0, 1, 2], target = 1

Output

Iteration 1:
  low=0, high=6, mid=3
  nums[0]=4, nums[3]=7, nums[6]=2
  Check: nums[0] ≤ nums[3]? 4 ≤ 7? YES → Left half sorted
  Check: 4 ≤ 1 < 7? NO (1 < 4) → Target NOT in sorted left half
  Action: low = mid + 1 = 4

Iteration 2:
  low=4, high=6, mid=5
  nums[4]=0, nums[5]=1, nums[6]=2
  Check: nums[mid] == target? 1 == 1? YES!
  
Result: Found at index 5 ✓

Explanation

The algorithm correctly recognizes that 1 is not in [4,5,6,7] and searches the right half.

Example 3: Target not present

Array: [4, 5, 6, 7, 0, 1, 2], Target: 3

Searching for 3 in [4, 5, 6, 7, 0, 1, 2]Target does not exist in the array.

Input

nums = [4, 5, 6, 7, 0, 1, 2], target = 3

Output

Iteration 1:
  low=0, high=6, mid=3
  Left half [4,5,6,7] sorted
  3 not in [4,7] → low = 4

Iteration 2:
  low=4, high=6, mid=5
  nums[4]=0 ≤ nums[5]=1? YES → Left half sorted
  0 ≤ 3 < 1? NO (3 > 1) → low = 6
  
Iteration 3:
  low=6, high=6, mid=6
  nums[mid]=2 ≠ 3
  nums[6]=2 ≤ nums[6]=2? YES → Left half sorted
  2 ≤ 3 < 2? NO → low = 7
  
low > high → Exit loop
Result: Not found, return -1

Explanation

After 3 iterations, the search space is exhausted. The algorithm correctly returns -1.

Common Mistakes and How to Avoid Them

This algorithm has several subtle pitfalls that trip up even experienced developers. Understanding these common mistakes will help you implement it correctly under interview pressure.

Common Mistakes

•Mistake 1: Using < instead of <= in nums[low] <= nums[mid] When low == mid (subarray of size 1-2), using strict < fails. The single element is both the left half and trivially sorted. Use <= to handle this correctly.
•Mistake 2: Off-by-one in range checks For left half: use nums[low] <= target < nums[mid] (exclude mid, we already checked it). For right half: use nums[mid] < target <= nums[high] (exclude mid, we already checked it). Getting these boundaries wrong causes infinite loops or missed elements.
•Mistake 3: Integer overflow in mid calculation In Java/C++, (low + high) / 2 can overflow. Always use low + (high - low) / 2. Python handles big integers automatically, but the habit is worth developing.
•Mistake 4: Forgetting to check if nums[mid] == target first Always check for the target at mid before deciding which half to search. Missing this causes you to skip the target when it's exactly at mid.
•Mistake 5: Wrong loop condition Use while (low <= high), not while (low < high). The condition low == high represents a subarray with exactly one element that must be checked.

wrong_approach.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# ❌ WRONG: Common mistakes combined
 
def search_buggy(nums, target):
    low, high = 0, len(nums) - 1
    
    # Bug 1: low < high misses last element
    while low < high:
        # Bug 2: Potential overflow in other langs
        mid = (low + high) // 2
        
        # Bug 3: Using < instead of <=
        if nums[low] < nums[mid]:
            # Bug 4: Wrong range bounds
            if nums[low] <= target <= nums[mid]:
                high = mid  # Bug 5: Should be mid-1
            else:
                low = mid  # Bug 6: Should be mid+1
        # ... more bugs likely
 
# This will fail on many cases!

correct_approach.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
# ✅ CORRECT: All pitfalls avoided
 
def search_correct(nums, target):
    low, high = 0, len(nums) - 1
    
    # Correct: <= to check single element
    while low <= high:
        # Correct: Overflow-safe
        mid = low + (high - low) // 2
        
        # Correct: Check target first
        if nums[mid] == target:
            return mid
        
        # Correct: <= handles low==mid
        if nums[low] <= nums[mid]:
            # Correct: Exclude mid with <
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        # ... symmetrical for right half
 
# This handles all edge cases!

Verification and Testing Strategy

In an interview, you should briefly mention how you'd verify your solution. A systematic testing strategy demonstrates engineering maturity.

Categories of test cases:

Essential Test Cases

•Empty array: Should return -1
•Single element — target present: Should return 0
•Single element — target absent: Should return -1
•Two elements — various rotations: Test [1,2], [2,1] with target in each position
•No rotation (fully sorted): Ensures algorithm works on edge case
•Target at start: First element is the target
•Target at end: Last element is the target
•Target at rotation point: Minimum element is the target
•Target at maximum (before rotation point): Maximum element is the target
•Target in left portion: Higher values, left of rotation point
•Target in right portion: Lower values, right of rotation point
•Target not present — would be in left portion:
•Target not present — would be in right portion:
•Target not present — smaller than minimum:
•Target not present — larger than maximum:

test_rotated_search.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
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
75
76
77
78
def run_comprehensive_tests(search_fn):
    """Test suite for rotated array search."""
    
    test_cases = [
        # (array, target, expected_index, description)
        ([], 1, -1, "Empty array"),
        ([5], 5, 0, "Single element - present"),
        ([5], 3, -1, "Single element - absent"),
        ([1, 2], 1, 0, "Two elements sorted - first"),
        ([1, 2], 2, 1, "Two elements sorted - second"),
        ([2, 1], 2, 0, "Two elements rotated - first"),
        ([2, 1], 1, 1, "Two elements rotated - second"),
        ([2, 1], 3, -1, "Two elements rotated - absent"),
        ([1, 2, 3, 4, 5], 3, 2, "Not rotated - middle"),
        ([4, 5, 6, 7, 0, 1, 2], 4, 0, "Target at start"),
        ([4, 5, 6, 7, 0, 1, 2], 2, 6, "Target at end"),
        ([4, 5, 6, 7, 0, 1, 2], 0, 4, "Target at rotation point (min)"),
        ([4, 5, 6, 7, 0, 1, 2], 7, 3, "Target at max (before rotation)"),
        ([4, 5, 6, 7, 0, 1, 2], 5, 1, "Target in left portion"),
        ([4, 5, 6, 7, 0, 1, 2], 1, 5, "Target in right portion"),
        ([4, 5, 6, 7, 0, 1, 2], 3, -1, "Absent - would be in right"),
        ([4, 5, 6, 7, 0, 1, 2], 8, -1, "Absent - larger than max"),
        ([4, 5, 6, 7, 0, 1, 2], -1, -1, "Absent - smaller than min"),
        ([5, 1, 2, 3, 4], 1, 1, "Rotation near start"),
        ([2, 3, 4, 5, 1], 1, 4, "Rotation near end"),
    ]
    
    print("Running Comprehensive Test Suite")
    print("=" * 70)
    
    passed = 0
    failed = 0
    
    for arr, target, expected, desc in test_cases:
        result = search_fn(arr, target)
        status = "✓" if result == expected else "✗"
        
        if result == expected:
            passed += 1
        else:
            failed += 1
            print(f"{status} FAIL: {desc}")
            print(f"    Array: {arr}, Target: {target}")
            print(f"    Expected: {expected}, Got: {result}")
    
    print(f"\nResults: {passed} passed, {failed} failed")
    return failed == 0
 
 
# Run tests
from typing import List
 
def search(nums: List[int], target: int) -> int:
    if not nums:
        return -1
    
    low, high = 0, len(nums) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if nums[mid] == target:
            return mid
        
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    
    return -1
 
run_comprehensive_tests(search)

Summary: The Complete Strategy

We've built a complete, production-ready algorithm for searching in rotated sorted arrays. Let's consolidate the key points:

Key Takeaways

•The algorithm is standard binary search with one twist: Before searching a half, determine which half is sorted.
•Use nums[low] <= nums[mid] to detect if left half is sorted. This handles all edge cases including single elements.
•For the sorted half, check if target is in its range. If yes, search there. If no, search the other half.
•Always check nums[mid] == target first before deciding which direction to go.
•Use low <= high as the loop condition to handle single-element subarrays.
•Use low + (high - low) // 2 for mid calculation to prevent overflow.
•Time complexity remains O(log n) — we still eliminate half the search space each iteration.
•Space complexity is O(1) for iterative, O(log n) for recursive.

What's next:

Page Complete