LeetCopilot Logo
LeetCopilot
LeetCode Pattern/Binary Search/Binary Search on Rotated Sorted Arrays: Complete Guide with Templates

Binary Search on Rotated Sorted Arrays: Complete Guide with Templates

LeetCopilot Team
Dec 30, 2025
16 min read
Binary SearchRotated ArrayTemplatesInterview PrepLeetCode
Master binary search on rotated sorted arrays with production-ready templates. Learn the key insight that one half is always sorted, how to identify it, and handle duplicates correctly.
Complete Guide

The Complete Binary Search Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to binary search. Learn all variants (classic, binary search on answer, rotated arrays), when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any binary search problem.

Read the complete guide

Rotated sorted array problems are among the most common binary search variations in technical interviews. They appear at Google, Facebook, Amazon, and virtually every FAANG company.

The challenge? The array isn't fully sorted, so standard binary search fails. But there's an elegant insight: at least one half is always sorted. Once you understand this principle, you can solve an entire class of problems with confidence.

This comprehensive guide will teach you the complete rotated array pattern, production-ready templates, how to handle duplicates, and the exact decision logic that works every time.

TL;DR

Key insight: In a rotated sorted array, one half is always sorted.

Template:

python
left, right = 0, len(arr) - 1

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

return -1

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

What Is a Rotated Sorted Array?

Definition and Examples

A rotated sorted array is a sorted array that has been rotated around some pivot point.

Original sorted array:

code
[1, 2, 3, 4, 5, 6, 7]

Rotated at index 3:

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

Rotated at index 5:

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

Key properties:

  • Elements before pivot: sorted and > elements after pivot
  • Elements after pivot: sorted
  • Overall: two sorted subarrays concatenated

Visual Representation

code
Original:  [1, 2, 3, 4, 5, 6, 7]
           ───────────────────────
              Fully sorted

Rotated:   [4, 5, 6, 7, 1, 2, 3]
           ───────────  ───────
            Sorted      Sorted
           (larger)    (smaller)

Why Standard Binary Search Fails

Standard binary search assumes:

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

This breaks on rotated arrays:

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

mid = 3, arr[3] = 7
7 > 2, so standard binary search goes left
But target 2 is actually in the right half!

The Core Insight

One Half Is Always Sorted

The key observation: At any mid point, at least one half (left or right) is always sorted.

Why? The rotation creates at most one "break point" where a larger number is followed by a smaller number. This break point can only be in one half.

Visual proof:

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

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

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

Left half:  [6, 7, 1, 2]  ← Not sorted (break at 7→1)
Right half: [3, 4, 5]     ← Sorted ✓

Decision Logic

Step 1: Identify which half is sorted

  • Compare arr[left] with arr[mid]
  • If arr[left] <= arr[mid]: left half is sorted
  • Otherwise: right half is sorted

Step 2: Check if target is in the sorted half

  • If yes: search in sorted half (normal binary search logic)
  • If no: search in unsorted half (which also has a sorted portion)

Example:

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

mid = 3, arr[mid] = 7

Step 1: Is left half sorted?
  arr[0] = 4 <= arr[3] = 7 → Yes, left half [4,5,6,7] is sorted

Step 2: Is target in sorted left half?
  4 <= 2 < 7? No
  → Target must be in right half

Search right half: [1, 2, 3]

Template: Search in Rotated Sorted Array

Python Template

python
def search(nums: List[int], target: int) -> int:
    """
    Search for target in rotated sorted array
    
    Time: O(log n)
    Space: O(1)
    
    Returns: Index of target, or -1 if not found
    """
    if not nums:
        return -1
    
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # Found target
        if nums[mid] == target:
            return mid
        
        # Determine which half is sorted
        if nums[left] <= nums[mid]:
            # Left half is sorted: [left...mid]
            if nums[left] <= target < nums[mid]:
                # Target is in sorted left half
                right = mid - 1
            else:
                # Target is in unsorted right half
                left = mid + 1
        else:
            # Right half is sorted: [mid...right]
            if nums[mid] < target <= nums[right]:
                # Target is in sorted right half
                left = mid + 1
            else:
                # Target is in unsorted left half
                right = mid - 1
    
    return -1

JavaScript Template

javascript
function search(nums, target) {
    if (!nums || nums.length === 0) return -1;
    
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] === target) {
            return mid;
        }
        
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

Java Template

java
public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        }
        
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

Pattern 1: Search Target (LeetCode #33)

Problem

Given a rotated sorted array and a target, find the index of the target.

Solution Walkthrough

python
def search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        if nums[left] <= nums[mid]:
            # Left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

# Examples
print(search([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))  # -1
print(search([1], 0))  # -1

Step-by-Step Trace

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

Iteration 1:
  left=0, right=6, mid=3
  nums[3]=7 != 0
  nums[0]=4 <= nums[3]=7 → left half sorted
  4 <= 0 < 7? No → search right half
  left=4

Iteration 2:
  left=4, right=6, mid=5
  nums[5]=1 != 0
  nums[4]=0 <= nums[5]=1 → left half sorted
  0 <= 0 < 1? Yes → search left half
  right=4

Iteration 3:
  left=4, right=4, mid=4
  nums[4]=0 == 0 → Found! Return 4 ✓

Edge Cases

1. Single element:

python
search([1], 1)  # 0
search([1], 2)  # -1

2. No rotation (fully sorted):

python
search([1, 2, 3, 4, 5], 3)  # 2

3. Target at pivot:

python
search([4, 5, 6, 7, 0, 1, 2], 4)  # 0
search([4, 5, 6, 7, 0, 1, 2], 0)  # 4

Pattern 2: Search with Duplicates (LeetCode #81)

How Duplicates Break the Pattern

The problem: When nums[left] == nums[mid], we can't determine which half is sorted.

Example:

code
Array: [1, 0, 1, 1, 1], target = 0

mid = 2, nums[mid] = 1
nums[left] = 1 == nums[mid] = 1

Is left half sorted? Can't tell!
  Could be: [1, 0, 1] (not sorted)
  Could be: [1, 1, 1] (sorted)

Modified Template

python
def search(nums: List[int], target: int) -> bool:
    """
    Search in rotated sorted array with duplicates
    
    Time: O(log n) average, O(n) worst case
    Space: O(1)
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return True
        
        # Handle duplicates: shrink search space
        if nums[left] == nums[mid] == nums[right]:
            left += 1
            right -= 1
        elif nums[left] <= nums[mid]:
            # Left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return False

# Example
print(search([2, 5, 6, 0, 0, 1, 2], 0))  # True
print(search([2, 5, 6, 0, 0, 1, 2], 3))  # False

Worst-Case Time Complexity

With duplicates: O(n) in worst case

Worst case example:

code
Array: [1, 1, 1, 1, 1, 1, 1, 0, 1], target = 0

All elements are 1 except one 0
Must check almost all elements → O(n)

See detailed guide: Duplicates in Rotated Arrays

Pattern 3: Find Minimum (LeetCode #153, #154)

Problem

Find the minimum element in a rotated sorted array.

Solution

python
def findMin(nums: List[int]) -> int:
    """
    Find minimum in rotated sorted array
    
    Time: O(log n)
    Space: O(1)
    """
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            # Minimum is in right half
            # (rotation point is to the right)
            left = mid + 1
        else:
            # Minimum is in left half or at mid
            right = mid
    
    return nums[left]

# Examples
print(findMin([3, 4, 5, 1, 2]))  # 1
print(findMin([4, 5, 6, 7, 0, 1, 2]))  # 0
print(findMin([11, 13, 15, 17]))  # 11 (no rotation)

Why This Works

Key insight: The minimum is always at or after the rotation point.

Decision logic:

  • If nums[mid] > nums[right]: rotation point is to the right
  • Otherwise: rotation point is to the left or mid is the minimum

Visual:

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

nums[3]=7 > nums[6]=2
→ Minimum is in right half

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

nums[3]=1 < nums[6]=5
→ Minimum is in left half or at mid

With Duplicates (LeetCode #154)

python
def findMin(nums: List[int]) -> int:
    """
    Find minimum with duplicates
    
    Time: O(log n) average, O(n) worst case
    """
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            left = mid + 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            # nums[mid] == nums[right], can't determine
            right -= 1  # Shrink search space
    
    return nums[left]

# Example
print(findMin([2, 2, 2, 0, 1]))  # 0

Common Mistakes

Mistake 1: Wrong Sorted Half Detection

❌ Wrong:

python
if nums[left] < nums[mid]:  # WRONG: should be <=
    # Left half sorted

Problem: When nums[left] == nums[mid], neither branch is taken correctly.

✅ Correct:

python
if nums[left] <= nums[mid]:
    # Left half sorted

Mistake 2: Incorrect Range Updates

❌ Wrong:

python
if nums[left] <= target < nums[mid]:
    left = mid + 1  # WRONG: should be right = mid - 1

✅ Correct:

python
if nums[left] <= target < nums[mid]:
    right = mid - 1  # Target in left half

Mistake 3: Not Handling Duplicates

❌ Wrong:

python
# Using template without duplicate handling on array with duplicates

✅ Correct:

python
if nums[left] == nums[mid] == nums[right]:
    left += 1
    right -= 1

See guide: Rotated Array Proof

Practice Problems

Master rotated arrays with these:

Beginner:

  1. Search in Rotated Sorted Array (#33) — Basic template
  2. Find Minimum in Rotated Sorted Array (#153) — Find minimum

Intermediate:
3. Search in Rotated Sorted Array II (#81) — With duplicates
4. Find Minimum in Rotated Sorted Array II (#154) — Find min with duplicates

Advanced:
5. Find Peak Element (#162) — Similar logic
6. Search in Rotated Sorted Array (custom variations) — Interview variations

Complexity Analysis

Time Complexity:

  • Without duplicates: O(log n) — Standard binary search
  • With duplicates: O(log n) average, O(n) worst case

Space Complexity: O(1) — Only use constant extra space

Comparison:

  • Linear search: O(n) always
  • Rotated binary search: O(log n) usually, O(n) worst case with duplicates

FAQ

Q: How do I know which half is sorted?

A: Compare nums[left] with nums[mid]. If nums[left] <= nums[mid], left half is sorted. Otherwise, right half is sorted.

Q: Why does this only work on rotated sorted arrays?

A: The key property is that one half is always sorted. This only holds for rotated sorted arrays, not arbitrary arrays.

Q: What if the array has duplicates?

A: Use the modified template that handles nums[left] == nums[mid] == nums[right] by shrinking the search space. Worst case becomes O(n).

Q: Can I use this for finding the rotation point?

A: Yes! The rotation point is where nums[i] > nums[i+1]. Or use the "find minimum" approach.

Q: What if there's no rotation (array is fully sorted)?

A: The algorithm still works! One half will always be sorted, and you'll find the target normally.

Conclusion

Binary search on rotated sorted arrays is a powerful technique built on one key insight: one half is always sorted.

Key principles:

  • Identify sorted half: Compare nums[left] with nums[mid]
  • Check if target is in sorted half: Use normal binary search logic
  • Search appropriate half: Sorted or unsorted
  • Handle duplicates: Shrink search space when ambiguous

The template:

python
if nums[left] <= nums[mid]:
    # Left half sorted
    if nums[left] <= target < nums[mid]:
        right = mid - 1
    else:
        left = mid + 1
else:
    # Right half sorted
    if nums[mid] < target <= nums[right]:
        left = mid + 1
    else:
        right = mid - 1

When to use:

  • Array is rotated sorted
  • Need O(log n) search
  • Can identify sorted portion

Master this pattern, and you'll solve rotated array problems with confidence. For more details, see Rotated Array Proof, Duplicates in Rotated Arrays, and the Complete Binary Search Guide.

Next time you see a rotated sorted array, remember: one half is always sorted.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials