Solving Search in Rotated Array in Python: Step-by-Step Guide

Introduction to Search in Rotated Sorted Array

The "Search in Rotated Sorted Array" problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. It tests your understanding of binary search, array manipulation, and your ability to adapt standard algorithms to non-standard scenarios. In this tutorial, we will walk through everything you need to know to solve this problem efficiently in Python.

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, consider the sorted array [0, 1, 2, 3, 4, 5, 6, 7]. If we rotate it at pivot index 3, we get [3, 4, 5, 6, 7, 0, 1, 2]. Notice that the array still contains two sorted sub-arrays, but the overall array is no longer fully sorted.

The challenge is to search for a target value in this rotated array efficiently, ideally in O(log n) time complexity, rather than the O(n) time a linear scan would require.

Why This Problem Matters

This problem is important for several reasons. First, it demonstrates mastery of binary search, one of the most fundamental algorithms in computer science. Second, it appears frequently in technical interviews at major tech companies because it reveals how well a candidate can reason about edge cases and modify standard algorithms. Finally, the underlying concept has practical applications in systems that use circular buffers, ring buffers, or log files that wrap around, where data is partially ordered but not fully sorted.

Understanding the Core Insight

The key insight is that even though the array is rotated, at least one half of the array (either the left half or the right half from the middle element) will always be sorted. By identifying which half is sorted, we can determine whether the target lies within that sorted half or the other half, and adjust our search boundaries accordingly.

Let us break this down step by step:

Find the middle element of the current search range.
Determine whether the left half or the right half is sorted.
Check if the target falls within the sorted half's range.
If it does, search that half; otherwise, search the other half.
Repeat until the target is found or the search range is exhausted.

Step-by-Step Implementation in Python

Now let us implement the solution. We will build it up gradually so you understand each piece.

Step 1: Setting Up the Function Signature

We need a function that accepts the rotated array and a target value, then returns the index of the target if found, or -1 if not found.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    return -1

Step 2: Implementing the Binary Search Loop

We use two pointers, left and right, to define our search range. In each iteration, we compute the middle index and compare the middle element with the target.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        
        # More logic here
        
    return -1

Step 3: Identifying the Sorted Half

This is the crucial step. We compare nums[left] with nums[mid]. If nums[left] <= nums[mid], the left half is sorted. Otherwise, the right half is sorted.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        
        # Check if 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

Step 4: Testing the Solution

Let us test our function with several cases to make sure it works correctly.

if __name__ == "__main__":
    # Test case 1: Target exists in the array
    nums1 = [4, 5, 6, 7, 0, 1, 2]
    print(search_rotated(nums1, 0))  # Output: 4
    
    # Test case 2: Target does not exist
    nums2 = [4, 5, 6, 7, 0, 1, 2]
    print(search_rotated(nums2, 3))  # Output: -1
    
    # Test case 3: Single element array
    nums3 = [1]
    print(search_rotated(nums3, 1))  # Output: 0
    
    # Test case 4: Array with two elements
    nums4 = [3, 1]
    print(search_rotated(nums4, 1))  # Output: 1
    
    # Test case 5: Non-rotated array
    nums5 = [1, 2, 3, 4, 5]
    print(search_rotated(nums5, 3))  # Output: 2

Handling Duplicates in the Array

The solution above works perfectly when all elements are distinct. However, if the array contains duplicates, there is a tricky edge case. Consider the array [2, 2, 2, 3, 2, 2, 2] with target 3. When nums[left] == nums[mid] == nums[right], we cannot determine which half is sorted. In this case, we simply shrink the search range by moving both pointers inward.

Modified Solution for Duplicates

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 mid
        
        # Handle the duplicate edge case
        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 -1

Note that when duplicates are present, the worst-case time complexity degrades to O(n) because we may need to skip many duplicate elements one by one. The average case remains O(log n).

Alternative Approach: Find Pivot First

Another valid approach is to first find the pivot point (the index where the rotation occurs), and then perform a standard binary search on the appropriate sorted half. This two-step approach is more intuitive for some developers.

Finding the Pivot Index

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

def search_with_pivot(nums, target):
    if not nums:
        return -1
    
    pivot = find_pivot(nums)
    left, right = 0, len(nums) - 1
    
    # Determine which sorted portion to search
    if target >= nums[pivot] and target <= nums[right]:
        left = pivot
    else:
        right = pivot - 1
    
    # Standard binary search
    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

This approach is slightly longer but separates concerns nicely. The pivot-finding step runs in O(log n), and the binary search also runs in O(log n), so the overall complexity remains the same.

Best Practices and Common Pitfalls

Best Practices

Always test edge cases: Empty arrays, single-element arrays, two-element arrays, and non-rotated arrays should all be tested.
Use clear variable names: Names like left, right, and mid make the code self-documenting.
Be careful with boundary conditions: Pay close attention to whether you use < or <= in comparisons, as off-by-one errors are the most common bugs in binary search.
Consider integer overflow: In languages like Java or C++, computing (left + right) // 2 can overflow. In Python, integers have arbitrary precision, so this is not a concern, but it is good to be aware of for cross-language work.
Clarify the problem with your interviewer: Always ask whether duplicates are allowed, whether the array is sorted in ascending or descending order, and what should be returned when the target is not found.

Common Pitfalls

Forgetting the equality check: When checking if the left half is sorted, you must use nums[left] <= nums[mid], not strict inequality, because left and mid can be the same index when the search range has only one or two elements.
Incorrect boundary updates: Make sure you update left = mid + 1 and right = mid - 1, not left = mid or right = mid, to avoid infinite loops.
Ignoring the duplicate case: If the problem allows duplicates and you do not handle the nums[left] == nums[mid] == nums[right] case, your algorithm may return incorrect results.

Complexity Analysis

Let us summarize the time and space complexity of our solutions:

Time complexity (distinct elements): O(log n) — each iteration halves the search space.
Time complexity (with duplicates, worst case): O(n) — when most elements are duplicates, we may need to skip them one at a time.
Space complexity: O(1) — we only use a constant amount of extra space for the pointers.

Conclusion

Solving the search in rotated sorted array problem is a rite of passage for any developer studying algorithms. By understanding that at least one half of a rotated array is always sorted, you can adapt binary search to handle this seemingly complex scenario with elegance and efficiency. Whether you choose the single-pass approach that identifies the sorted half in each iteration, or the two-step approach that first locates the pivot, the key is to reason carefully about boundary conditions and edge cases. Practice this problem until the logic becomes second nature, as the same pattern of modifying binary search appears in many other algorithmic challenges, and mastering it will serve you well in both interviews and real-world development.