Search in Rotated Array: Multiple Solutions and Complexity Analysis

Search in Rotated Sorted Array: Multiple Solutions and Complexity Analysis

Searching in a rotated sorted array is one of the most classic algorithmic interview problems. It tests your understanding of binary search, array manipulation, and edge-case reasoning. In this tutorial, we will explore what a rotated sorted array is, why this problem matters, and walk through multiple solutions with detailed complexity analysis.

What Is a Rotated Sorted Array?

A rotated sorted array is an array that was originally sorted in ascending order but has been "rotated" at some pivot point. For example, if you take the sorted array [0, 1, 2, 3, 4, 5, 6, 7] and rotate it at index 3, you get [3, 4, 5, 6, 7, 0, 1, 2]. The rotation shifts elements from one end to the other while preserving the relative order within each segment.

The challenge is to find a target element in this rotated array efficiently. A naive linear scan would work in O(n) time, but the goal is to leverage the partial ordering to achieve O(log n) time using a modified binary search.

Why This Problem Matters

This problem is important for several reasons:

Real-world relevance: Rotated arrays appear in circular buffers, log files that wrap around, and load-balanced systems where data is partitioned cyclically.
Algorithmic thinking: It forces you to adapt a well-known algorithm (binary search) to a non-standard scenario, sharpening your ability to reason about invariants.
Interview staple: It is one of the most frequently asked questions in technical interviews at major tech companies.
Foundation for variants: Understanding this problem prepares you for related challenges like searching in rotated arrays with duplicates, finding the rotation point, or searching in a circular array.

Problem Statement

Given a rotated sorted array of distinct integers and a target value, return the index of the target if it exists in the array, otherwise return -1. The algorithm should run in O(log n) time.

Solution 1: Find Pivot Then Binary Search

The first approach breaks the problem into two steps: first, find the pivot index where the rotation occurs, then perform a standard binary search on the appropriate half of the array.

Step 1: Finding the Pivot

The pivot is the smallest element in the array, which is also the point where the array transitions from the larger segment to the smaller segment. We can find it using binary search by comparing the middle element with the rightmost element.

def find_pivot(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return left

Step 2: Binary Search on the Correct Half

Once we know the pivot, we can determine which half of the array the target lies in by comparing the target with the first and last elements. Then we perform a standard binary search on that segment.

def search_rotated(nums, target):
    if not nums:
        return -1
    
    pivot = find_pivot(nums)
    n = len(nums)
    
    # Decide which half to search
    if target >= nums[0]:
        # Search left portion (0 to pivot-1)
        left, right = 0, pivot - 1
    else:
        # Search right portion (pivot to n-1)
        left, right = pivot, n - 1
    
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Complexity Analysis

This two-step approach runs two binary searches sequentially. Finding the pivot takes O(log n) time, and the subsequent binary search also takes O(log n) time. The total time complexity is O(log n), and the space complexity is O(1) since we only use a few variables.

One edge case to consider: when the array is not rotated at all (pivot is 0), the condition target >= nums[0] still works correctly because the entire array is sorted and the left portion covers the whole array.

Solution 2: Single-Pass Modified Binary Search

The second approach is more elegant: it combines both steps into a single binary search. The key insight is that in a rotated sorted array, at least one half of the array (either the left half or the right half of the midpoint) is always properly sorted. We can determine which half is sorted and then decide whether the target lies within that sorted half.

The Algorithm

At each step, compare the middle element with the leftmost element to determine which half is sorted. Then check if the target falls within the range of the sorted half. If it does, search that half; otherwise, search the other half.

def search_rotated_single_pass(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        
        # Check if the left half is sorted
        if nums[left] <= nums[mid]:
            # Target is in the sorted left half
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

How It Works

Let us trace through an example. Consider the array [4, 5, 6, 7, 0, 1, 2] with target 0:

Initially, left = 0, right = 6, mid = 3. nums[mid] = 7. Since nums[0] = 4 <= 7, the left half [4, 5, 6, 7] is sorted. The target 0 is not in range [4, 7), so we search the right half: left = 4.
Now left = 4, right = 6, mid = 5. nums[mid] = 1. Since nums[4] = 0 <= 1, the left half is sorted. The target 0 is in range [0, 1), so we search the left half: right = 4.
Now left = 4, right = 4, mid = 4. nums[mid] = 0, which equals the target. Return 4.

Complexity Analysis

This single-pass solution performs one binary search, giving a time complexity of O(log n) and a space complexity of O(1). It is more efficient in practice than the two-step approach because it halves the search space in every iteration without the overhead of a separate pivot-finding pass.

Solution 3: Recursive Approach

For completeness, here is a recursive implementation of the single-pass modified binary search. The logic is identical, but the structure may appeal to developers who prefer recursive solutions.

def search_rotated_recursive(nums, target):
    def helper(left, right):
        if left > right:
            return -1
        
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                return helper(left, mid - 1)
            else:
                return helper(mid + 1, right)
        else:
            if nums[mid] < target <= nums[right]:
                return helper(mid + 1, right)
            else:
                return helper(left, mid - 1)
    
    return helper(0, len(nums) - 1)

Complexity Analysis

The recursive solution has the same O(log n) time complexity. However, the space complexity is O(log n) due to the recursion stack, which grows proportionally to the depth of the recursive calls. In production environments with very large arrays, this could lead to stack overflow errors, making the iterative approach preferable.

Solution 4: Handling Duplicates

A common variant of this problem allows duplicate values in the array. This complicates the search because when nums[left] == nums[mid] == nums[right], we cannot determine which half is sorted. The solution is to shrink the search range by moving both pointers inward until we can make a determination.

def search_rotated_with_duplicates(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return True
        
        # When we cannot determine the sorted half
        if nums[left] == nums[mid] == nums[right]:
            left += 1
            right -= 1
        elif nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return False

Complexity Analysis with Duplicates

In the worst case, when all elements are the same except one, the algorithm degrades to O(n) time complexity because we may need to skip duplicates one by one. The space complexity remains O(1). This is an important distinction from the distinct-elements version, which guarantees O(log n) time.

Best Practices

When implementing search in a rotated sorted array, keep the following best practices in mind:

Prefer the single-pass iterative solution: It is the most efficient in both time and space, and avoids the overhead of recursion or a separate pivot-finding step.
Handle edge cases explicitly: Always check for empty arrays, single-element arrays, and arrays that are not actually rotated (pivot at index 0).
Use inclusive bounds carefully: The condition nums[left] <= nums[mid] uses <= to handle the case where left == mid, which occurs when there are only two elements in the search range.
Test with diverse inputs: Verify your solution with arrays rotated at different positions, targets at the boundaries, and targets not present in the array.
Clarify constraints with interviewers: Always ask whether duplicates are allowed, as this significantly affects the algorithm and its complexity.

Performance Comparison

Here is a summary of the different solutions and their complexities:

| Solution                    | Time Complexity | Space Complexity | Notes                              |
|-----------------------------|-----------------|------------------|------------------------------------|
| Find pivot + binary search  | O(log n)        | O(1)             | Two passes, conceptually simpler   |
| Single-pass iterative       | O(log n)        | O(1)             | Most efficient, recommended        |
| Recursive                   | O(log n)        | O(log n)         | Stack overhead, risk of overflow   |
| With duplicates             | O(n) worst case | O(1)             | Degrades when many duplicates      |

Conclusion

Searching in a rotated sorted array is a powerful problem that deepens your understanding of binary search and adaptive algorithms. The single-pass iterative solution is the most practical choice, offering optimal O(log n) time and O(1) space complexity while handling all edge cases cleanly. When duplicates are involved, the algorithm must gracefully degrade, and understanding why this happens is just as important as knowing the solution itself. By mastering these techniques, you not only prepare yourself for technical interviews but also build a foundation for solving more complex search and partitioning problems in real-world applications.