Why Binary Search Works on Rotated Sorted Arrays (Visual Proof)

Understanding why binary search works on rotated sorted arrays is more valuable than memorizing the template. Once you grasp the underlying principle, you can derive the solution from first principles in any interview.

The key insight is deceptively simple: in a rotated sorted array, at least one half is always sorted. But why is this true? And how does it enable binary search?

This guide provides the complete mathematical proof, visual examples, and the intuition behind why this elegant algorithm works.

TL;DR

The proof in three steps:

1. Rotation creates at most one break point (where a larger number is followed by a smaller number)
2. One break point means one half has no break (i.e., is sorted)
3. We can identify the sorted half and use normal binary search logic on it

Visual:

[4, 5, 6, 7, 1, 2, 3]
          ↑
      break point

Left of any mid:  Either has break or doesn't
Right of any mid: Either has break or doesn't
At most one half has the break → Other half is sorted

The Key Insight: One Half Is Always Sorted

Statement

Theorem: In a rotated sorted array, when you pick any index mid, at least one of the two halves [left, mid] or [mid, right] is sorted.

Proof

Given: A sorted array that has been rotated

Step 1: Rotation creates exactly one break point

A break point is an index i where arr[i] > arr[i+1].

In a sorted array: No break points

[1, 2, 3, 4, 5, 6, 7]
No i where arr[i] > arr[i+1]

After rotation: Exactly one break point

[4, 5, 6, 7, 1, 2, 3]
          ↑
      7 > 1 (break point)

Why exactly one? Rotation moves a contiguous block from the end to the beginning. This creates one discontinuity where the end of the moved block meets the start of the remaining block.

Step 2: One break point can only be in one half

When we pick a mid point, we divide the array into two halves:

• Left half: [left, mid]
• Right half: [mid, right]

The break point (if it exists) is at a specific index. It can only be in one of these halves, not both.

Step 3: The half without the break point is sorted

If a subarray has no break point, it's sorted (by definition of break point).

Conclusion: At least one half is always sorted. ∎

Visual Proof

Example 1:

Array: [4, 5, 6, 7, 1, 2, 3]
                 ↑
                mid=3

Break point is between index 3 and 4 (7 > 1)

Left half:  [4, 5, 6, 7]  ← No break point → Sorted ✓
Right half: [1, 2, 3]     ← No break point → Sorted ✓

Both halves are sorted!

Example 2:

Array: [6, 7, 1, 2, 3, 4, 5]
                 ↑
                mid=3

Break point is between index 1 and 2 (7 > 1)

Left half:  [6, 7, 1, 2]  ← Has break point → Not sorted
Right half: [2, 3, 4, 5]  ← No break point → Sorted ✓

Right half is sorted!

Example 3:

Array: [3, 4, 5, 6, 7, 1, 2]
                 ↑
               mid=3

Break point is between index 4 and 5 (7 > 1)

Left half:  [3, 4, 5, 6]  ← No break point → Sorted ✓
Right half: [6, 7, 1, 2]  ← Has break point → Not sorted

Left half is sorted!

How to Identify the Sorted Half

The Decision Rule

Compare arr[left] with arr[mid]:

If arr[left] <= arr[mid]:

• Left half is sorted
• Why? No element in [left, mid] is greater than the next

If arr[left] > arr[mid]:

• Right half is sorted
• Why? The break point is in the left half, so right half has no break

Mathematical Justification

Case 1: arr[left] <= arr[mid]

For the left half to be unsorted, there must be an index i in [left, mid) where arr[i] > arr[i+1].

But if such an i exists:

• arr[i] > arr[i+1] (break point)
• arr[i+1] <= ... <= arr[mid] (after break, values increase)
• This means arr[mid] < arr[i]
• But arr[left] <= arr[i] (before break, values increase)
• So arr[left] <= arr[i] and arr[mid] < arr[i]
• Therefore arr[left] > arr[mid] (contradiction!)

So if arr[left] <= arr[mid], the left half must be sorted.

Case 2: arr[left] > arr[mid]

This means the break point is in the left half (between left and mid).

Since there's only one break point in the entire array, the right half has no break point, so it's sorted.

Visual Examples

Example 1: Left half sorted

Array: [4, 5, 6, 7, 1, 2, 3]
        ↑        ↑
      left=0   mid=3

arr[0]=4 <= arr[3]=7 ✓
→ Left half [4, 5, 6, 7] is sorted

Example 2: Right half sorted

Array: [6, 7, 1, 2, 3, 4, 5]
        ↑        ↑
      left=0   mid=3

arr[0]=6 > arr[3]=2 ✓
→ Right half [2, 3, 4, 5] is sorted

Why Standard Binary Search Fails

The Problem

Standard binary search assumes:

• If arr[mid] < target, target must be in right half
• If arr[mid] > target, target must be in left half

This breaks on rotated arrays:

Array: [4, 5, 6, 7, 1, 2, 3], target = 2

mid = 3, arr[mid] = 7

Standard binary search logic:
  7 > 2 → search left half

But target 2 is in the right half!

Why It Breaks

Standard binary search relies on global ordering: if arr[mid] > target, all elements to the right are also > target.

Rotated arrays break this assumption:

[4, 5, 6, 7, 1, 2, 3]
          ↑
         mid=7

Elements to the right: [1, 2, 3]
Some are < 7, not all > 7!

How Rotated Binary Search Works

The Algorithm

Instead of relying on global ordering, we:

1. Identify which half is sorted (using arr[left] vs arr[mid])
2. Check if target is in the sorted half (using normal binary search logic)
3. Search the appropriate half

Why This Works

Key insight: We can use normal binary search logic on the sorted half.

Step-by-step:

Array: [4, 5, 6, 7, 1, 2, 3], target = 2

Iteration 1:
  left=0, right=6, mid=3
  arr[mid]=7
  
  Is left half sorted?
    arr[0]=4 <= arr[3]=7 ✓
    Left half [4, 5, 6, 7] is sorted
  
  Is target in sorted left half?
    4 <= 2 < 7? No
    → Target NOT in left half
    → Search right half
  
  left = 4

Iteration 2:
  left=4, right=6, mid=5
  arr[mid]=2
  
  arr[5]=2 == 2 → Found!

Proof of Correctness

Claim: The algorithm always finds the target if it exists.

Proof:

At each step, we either:

1. Find the target (return)
2. Eliminate half the search space

We eliminate the correct half because:

• If target is in the sorted half, we detect it (using normal binary search logic)
• If target is not in the sorted half, it must be in the other half

Since we halve the search space each time and always eliminate the correct half, we'll find the target in O(log n) time. ∎

Edge Cases and Special Scenarios

No Rotation (Fully Sorted)

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

At any mid:
  arr[left] <= arr[mid] (always true)
  → Left half is always sorted
  → Algorithm works like normal binary search

Rotation at Index 0 (No Change)

Array: [1, 2, 3, 4, 5, 6, 7]
Same as no rotation

Rotation at Last Index

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

Break point between index 0 and 1

At mid=3:
  arr[0]=7 > arr[3]=3
  → Right half [3, 4, 5, 6] is sorted

Single Element

Array: [1]

No rotation possible
Both halves are "sorted" (empty or single element)

Comparison with Other Approaches

Approach 1: Linear Search

Time: O(n)
Space: O(1)

Pros: Simple, always works
Cons: Slow, doesn't leverage sorted property

Approach 2: Find Rotation Point, Then Binary Search

Time: O(log n) + O(log n) = O(log n)
Space: O(1)

Pros: Intuitive
Cons: Two passes, more complex

Approach 3: Rotated Binary Search (Our Approach)

Time: O(log n)
Space: O(1)

Pros: Single pass, optimal
Cons: Requires understanding the sorted half property

Common Misconceptions

Misconception 1: "Both halves can be unsorted"

False. At most one half contains the break point. The other half is always sorted.

Misconception 2: "We need to find the rotation point first"

False. We can search directly without finding the rotation point.

Misconception 3: "This only works for specific rotation amounts"

False. It works for any rotation (0 to n-1).

Misconception 4: "The algorithm is O(n) in worst case"

False (for unique elements). It's always O(log n) when elements are unique. Only with duplicates can it degrade to O(n).

Practice: Derive the Algorithm

Try deriving the algorithm yourself:

Given: Rotated sorted array, target
Goal: Find target in O(log n)

Hints:

1. What property does the array have? (One half is always sorted)
2. How can you identify the sorted half? (Compare arr[left] with arr[mid])
3. How do you know if target is in the sorted half? (Normal binary search logic)
4. What do you do if target is not in the sorted half? (Search the other half)

Template:

while left <= right:
    mid = left + (right - left) // 2
    
    if arr[mid] == target:
        return mid
    
    # Which half is sorted?
    if arr[left] <= arr[mid]:
        # Left half sorted
        if arr[left] <= target < arr[mid]:
            # Target in sorted left half
            right = mid - 1
        else:
            # Target in unsorted right half
            left = mid + 1
    else:
        # Right half sorted
        if arr[mid] < target <= arr[right]:
            # Target in sorted right half
            left = mid + 1
        else:
            # Target in unsorted left half
            right = mid - 1

FAQ

Q: Why is there exactly one break point?

A: Rotation moves a contiguous block from end to beginning. This creates one discontinuity where the moved block meets the remaining array.

Q: Can both halves be sorted?

A: Yes! When the rotation point is not between left and right, both halves are sorted. The algorithm still works.

Q: What if the array has duplicates?

A: When arr[left] == arr[mid], we can't determine which half is sorted. We need to shrink the search space. See Duplicates in Rotated Arrays.

Q: Does this work for rotated arrays with negative numbers?

A: Yes! The algorithm only relies on the sorted property, not the actual values.

Conclusion

Binary search on rotated sorted arrays works because of one elegant property: at least one half is always sorted.

The proof:

1. Rotation creates exactly one break point
2. One break point can only be in one half
3. The other half has no break point → sorted

The algorithm:

1. Identify which half is sorted (arr[left] vs arr[mid])
2. Check if target is in sorted half (normal binary search)
3. Search appropriate half

Why it's O(log n):

• We eliminate half the search space each iteration
• We always eliminate the correct half
• log₂(n) iterations to find target

Understanding this proof gives you the confidence to derive the solution in any interview, handle edge cases correctly, and explain your reasoning clearly.

For implementation details, see Rotated Sorted Array Guide. For handling duplicates, see Duplicates in Rotated Arrays. For the complete binary search guide, see Binary Search Guide.

Next time you see a rotated sorted array, remember: one half is always sorted, and that's all you need.