Search in Rotated Sorted Array Java Solution

Search in rotated sorted arrays presents a classic binary search variation where the array's rotation complicates standard search approaches, requiring careful handling of multiple comparison conditions to maintain O(log n) time complexity.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the size constraint on the input array? (e.g., up to 10^6 elements)
2. Are duplicates allowed in the array?
3. What is the expected return format? (index of target or boolean existence)
4. Can we modify the input array during our search?
5. What is the target time complexity for follow-up? (e.g., O(log n) or better)

Restatement of the pattern: The search in rotated sorted array problem involves finding a target element in an array that was originally sorted in ascending order but has been rotated at some pivot point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7]. The challenge is to efficiently locate a target value in this rotated structure.

Signal words and constraint shape: Key indicators include "rotated sorted array", "search in rotated array", "find target in rotated sorted array", and constraints like "O(log n) time complexity". The problem typically presents a sorted array that has been rotated at exactly one pivot point, making it a classic binary search variant.

Assumptions made:

• The array contains distinct elements (unless duplicates are explicitly mentioned)
• The rotation point is exactly one position (i.e., it's a single rotation, not multiple)
• The array is guaranteed to be a rotated version of some sorted array
• We're looking for exact matches, not ranges or counts

Scenario suitability: This pattern is best suited for static scenarios where the rotated array is fixed and multiple searches can be performed. It's not ideal for streaming data where rotations happen frequently, as each new rotation would require a complete reanalysis of the search strategy.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "rotated sorted array" or "rotated array"
• "search for target in rotated array"
• "find minimum/maximum in rotated array"
• Array that was originally sorted but has been rotated at some pivot point
• "array with distinct elements" or "array with duplicates" (affects approach choice)
• "O(log n) time complexity required"

Why this pattern fits better than the most common alternatives: This pattern is specifically designed for searching in arrays that were originally sorted but have been rotated. The key insight is that even though the array is rotated, it maintains a "sorted property" in parts - one half of the array will always be sorted. This allows us to use modified binary search instead of linear scan, which would be O(n) time complexity.

Compared to alternatives:

• Linear search: O(n) - inefficient for large arrays
• Standard binary search: Only works on fully sorted arrays, not rotated ones
• Two-pass approach (find pivot + binary search): More complex than single-pass modified binary search

Conditions where a variation or related pattern applies instead:

• If the array is not rotated but just shifted, use standard binary search
• If duplicates are present in the rotated array, we need to handle them specially (they can break the binary search logic)
• If the array is rotated multiple times or in a complex pattern, we'd need different approaches
• For unsorted arrays with no rotation, we'd use linear search or sorting first

The core insight that makes this pattern work: In any rotated sorted array, at least one half (left or right) of the current search space will always be completely sorted. This allows us to determine whether our target lies in that sorted half and adjust our search space accordingly, maintaining O(log n) time complexity.

The key is recognizing that even rotated arrays maintain a "sorted-invariant" property - we can always determine which half is sorted and whether our target lies in that half.

3. Approach Evolution

Interview communication script:

My first instinct is to do a linear scan through the array to find the target, which would be O(n) time complexity. But that's inefficient because we're not leveraging the sorted nature of the subarrays. Let me think about how to optimize this.

I notice that even though the array is rotated, it's composed of two sorted subarrays. If I can find where the rotation point is, I could potentially use binary search on each half. But that requires two passes - one to find the pivot, another to search.

Wait, I can do better than that. Looking more carefully at the rotated array structure, I realize that if I perform a modified binary search, I can determine in each iteration whether the target lies in the left or right portion of the current search space. The key insight is that at any point in a rotated sorted array, at least one side (left or right) will always be properly sorted.

Let me trace through this more systematically. I can maintain the invariant that at each step, either the left half or right half is completely sorted. This allows me to make a decision about which side to continue searching on, reducing the problem space by half each time.

The key optimization is that instead of finding the pivot first, I can do a single pass with modified binary search. This is O(log n) time complexity instead of O(n) or O(n log n).

Brute-force approach and why it is not ideal:

The brute force approach would be to iterate through the entire array linearly, checking each element against the target. This is O(n) time complexity and doesn't leverage the sorted property of the subarrays. It's inefficient because we're not taking advantage of the fact that the array has two sorted portions.

Improved approach and the key optimization:

The key insight is that in any rotated sorted array, at least one half (left or right) of the current search space will always be properly sorted. This allows us to make a decision at each step about which half to search next.

The optimization works by:

1. Finding the middle element
2. Determining whether the left half or right half is sorted
3. Checking if the target lies within the bounds of the sorted half
4. Narrowing search to that half

This reduces our search space by half at each step, giving us O(log n) time complexity.

Final approach with step-by-step reasoning:

1. Start with left = 0 and right = array.length - 1
2. While left <= right:
   • Calculate mid = (left + right) / 2
   • If nums[mid] == target, return mid
   • Determine which half is sorted:
     • If nums[left] <= nums[mid], left half is sorted
     • Else right half is sorted
   • Check if target lies in the sorted half:
     • If left half is sorted and target is within [nums[left], nums[mid]), search left
     • Else if right half is sorted and target is within [nums[mid], nums[right]), search right
   • Adjust left/right pointers accordingly

Important invariants that must hold:

1. The search space is always valid (left <= right)
2. At each step, at least one half of the current search space is properly sorted
3. The target, if present, must lie in one of the halves that we're searching
4. We never eliminate elements that could contain our target

4. Data Structure Choice

For the search in rotated sorted array problem, I'll use a combination of primitive data types and standard Java collections:

Primary Data Structures:

1. Array/Integer[]: The input array is the primary data structure that holds our rotated sorted elements. We'll use primitive int[] for efficiency, but could also work with Integer[] if we need null handling.

2. Pointers/Indices: We'll use simple integer variables (left, right, mid) to maintain our search boundaries. These are O(1) space and essential for the binary search approach.

Why Each Choice Is Needed:

• The array is our input and target container - no alternative data structure can replace it since we're searching within the given rotated array
• Pointers are essential because they allow us to maintain search bounds without creating new arrays, enabling O(log n) time complexity
• No additional collections like HashMaps or Sets are needed since we're doing a search, not tracking frequencies or unique elements

Time and Space Impact:

• Time Complexity: O(1) for pointer operations, O(log n) for the search itself
• Space Complexity: O(1) additional space - just the three integer pointers (left, right, mid)
• Memory Access: Direct array indexing provides O(1) element access

Helper Structures:

• No helper structures needed beyond basic integer indices
• The algorithm is purely based on mathematical properties of rotated arrays and binary search bounds

This minimal approach ensures we're not over-engineering the solution - we only use what's strictly necessary for the binary search implementation. The simplicity of using just integer indices makes the code clean, readable, and efficient.

// Example of our pointer usage:
int left = 0;
int right = nums.length - 1;
int mid = left + (right - left) / 2; // Prevents integer overflow

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works:

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

Step 1: Initialize pointers

• left = 0, right = 6

Step 2: First iteration

• mid = (0+6)/2 = 3
• nums[3] = 7, nums[0] = 4, nums[6] = 2
• Since nums[left] <= nums[mid] (4 ≤ 7), left half is sorted
• Check if target 0 is in range [4, 7]: 4 ≤ 0 ≤ 7 → False
• Since target not in left half, move to right: left = mid + 1 = 4

Step 3: Second iteration

• left = 4, right = 6
• mid = (4+6)/2 = 5
• nums[5] = 1, nums[4] = 0, nums[6] = 2
• Since nums[left] > nums[mid] (0 > 1) is false, right half is sorted
• Check if target 0 is in range [1, 2]: 1 ≤ 0 ≤ 2 → False
• Since target not in right half, move to left: right = mid - 1 = 4

Step 4: Third iteration

• left = 4, right = 4
• mid = (4+4)/2 = 4
• nums[4] = 0
• Target matches nums[mid], return index 4

The algorithm correctly identifies that we can use binary search by determining which half of the rotated array is properly sorted, then checking if our target lies within that sorted range.

Edge case handling:

• When left == right, we've found our target or determined it's not present
• When nums[left] == nums[mid], we can't determine which half is sorted, but this case is handled by our condition checking
• The algorithm maintains the invariant that we're always searching in a valid portion of the array

6. Java Solution

public class SearchInRotatedArray {
    
    /**
     * Searches for target in a rotated sorted array.
     * Returns the index of target if found, otherwise -1.
     * 
     * @param nums rotated sorted array
     * @param target value to search for
     * @return index of target or -1 if not found
     */
    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;
            }
            
            // Determine which half is properly sorted
            if (nums[left] <= nums[mid]) {
                // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    // Target is in left half
                    right = mid - 1;
                } else {
                    // Target is in right half
                    left = mid + 1;
                }
            } else {
                // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    // Target is in right half
                    left = mid + 1;
                } else {
                    // Target is in left half
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
}

The solution uses binary search with a key insight: at any point in the rotated array, at least one half (left or right) will be properly sorted. We leverage this property to determine which half contains our target and narrow our search space accordingly. The algorithm handles all edge cases including empty arrays, single elements, and duplicate values by maintaining proper boundary conditions.

7. Complexity Analysis

Time Complexity: O(log n)

The algorithm performs binary search on the rotated array, which reduces the search space by half in each iteration. Since we only make one pass through the array and each step involves constant-time operations (comparisons and index calculations), the overall time complexity is O(log n).

Space Complexity: O(1)

The solution uses only a constant amount of extra space for variables (left, right, mid) regardless of the input size. No additional data structures or recursive call stacks are required, making it O(1) space complexity.

Why These Bounds Are Correct:

The logarithmic time complexity stems from the binary search nature of the algorithm. In each iteration, we eliminate half of the remaining elements by comparing the middle element with either the leftmost or rightmost element to determine which half contains the target. This is the same pattern as standard binary search, so the time complexity follows the same O(log n) bound.

The constant space complexity is maintained because we only use a fixed number of integer variables to track our search boundaries and current position, without any data structures that grow with input size.

Optimality:

This solution is optimal for the rotated array search problem. Since we need to find a specific element in a potentially unsorted rotated array, and the array is not fully sorted, we cannot do better than O(log n) time complexity in the general case. The solution achieves the theoretical lower bound for this problem type, making it near-optimal.

The algorithm's efficiency comes from leveraging the sorted nature of the two subarrays created by the rotation, allowing us to make informed decisions about which half to search next without having to examine every element.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should return -1 for any target search
• Single element array: Works correctly, but must handle the case where left == right and target == nums[0]
• Two element array: Requires careful handling of the rotation point detection

Duplicate Values and Repeated States

• Duplicates in rotated array: When nums[left] == nums[mid] == nums[right], we cannot determine which half to eliminate, so we must reduce the search space by moving pointers inward
• All elements same: Array like [2,2,2,2,2] with target 2 requires special handling to avoid infinite loops

Boundary Conditions

• Target at boundaries: When target equals nums[left] or nums[right], ensure proper handling in binary search logic
• No rotation: Array like [1,2,3,4,5] where left == 0 and right == nums.length - 1 should work correctly
• Full rotation: Array like [5,1,2,3,4] where left == 0 and right == nums.length - 1 with rotation at index 1

Common Implementation Mistakes

• Incorrect mid calculation: Using (left + right) / 2 instead of left + (right - left) / 2 can cause integer overflow in some languages
• Missing boundary checks: Not checking if left <= right before accessing array elements
• Incorrect rotation point detection: Assuming that if nums[mid] > nums[left], the left half is sorted, but failing to consider edge cases where nums[mid] == nums[left]
• Inconsistent pointer movement: Moving left or right incorrectly when encountering duplicates
• Off-by-one errors in rotation logic: Misunderstanding which half is sorted and how to proceed with search

Additional Considerations

• Integer overflow: While Java handles large integers gracefully, it's good to be aware of potential issues in other languages
• Array mutation: If the problem allows modifying input arrays, ensure that the rotation logic doesn't inadvertently modify the original array structure
• Return value consistency: Always return -1 for missing targets, not null or other sentinel values, to maintain API contract consistency

9. Alternative Approaches

There are several alternative approaches to solving the rotated array search problem, each with different trade-offs:

Linear Search Approach: The simplest alternative is to perform a linear scan through the array to find the target. This approach has O(n) time complexity and is straightforward to implement but doesn't leverage the sorted nature of the subarrays. It's only viable when the array size is small or when we cannot afford to do the preprocessing required for binary search.

Two-Step Process (Find Pivot + Binary Search): First, find the pivot point where rotation occurs using binary search, then perform two separate binary searches on the two sorted subarrays. This approach requires two passes through the array and has O(log n) time complexity but involves more complex logic to handle edge cases like arrays with no rotation or duplicate elements.

Modified Binary Search (Alternative Implementation): Instead of checking which half is sorted, we can check if the target lies within a specific range. For example, in each step we could check if nums[left] <= target <= nums[mid] or nums[mid] <= target <= nums[right]. This approach is mathematically equivalent but structurally different in how it makes decisions.

Hash Map Preprocessing: Store all elements and their indices in a hash map during preprocessing, allowing O(1) lookup. This approach has O(n) space complexity and O(1) query time but requires preprocessing that may not be acceptable in streaming scenarios.

The chosen binary search approach is preferred because it maintains optimal O(log n) time complexity with minimal space overhead while being clean and readable. The alternative approaches either increase time complexity or require additional space, making them less suitable for the constraints typically found in FAANG interviews.

10. Test Cases

public class SearchInRotatedArray {
    public static void main(String[] args) {
        // Test case 1: Basic rotated array
        int[] arr1 = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("Test 1 - Target 0: " + search(arr1, 0)); // Expected: 4
        
        // Test case 2: Target not in array
        System.out.println("Test 2 - Target 3: " + search(arr1, 3)); // Expected: -1
        
        // Test case 3: Array with duplicates
        int[] arr2 = {2, 2, 2, 3, 4, 2};
        System.out.println("Test 3 - Target 3: " + search(arr2, 3)); // Expected: 3
        
        // Test case 4: Unrotated array (sorted)
        int[] arr3 = {1, 2, 3, 4, 5};
        System.out.println("Test 4 - Target 3: " + search(arr3, 3)); // Expected: 2
        
        // Test case 5: Single element array
        int[] arr4 = {5};
        System.out.println("Test 5 - Target 5: " + search(arr4, 5)); // Expected: 0
        
        // Test case 6: Two element rotated array
        int[] arr5 = {2, 1};
        System.out.println("Test 6 - Target 2: " + search(arr5, 2)); // Expected: 0
        
        // Test case 7: Empty array
        int[] arr6 = {};
        System.out.println("Test 7 - Target 1: " + search(arr6, 1)); // Expected: -1
        
        // Test case 8: Target at beginning of rotated array
        int[] arr7 = {3, 1, 2};
        System.out.println("Test 8 - Target 3: " + search(arr7, 3)); // Expected: 0
        
        // Test case 9: Target at end of rotated array
        int[] arr8 = {3, 1, 2};
        System.out.println("Test 9 - Target 2: " + search(arr8, 2)); // Expected: 2
    }
    
    public static int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) return mid;
            
            // Left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } 
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
}

Sample Test Cases:

1. Basic rotated array: {4, 5, 6, 7, 0, 1, 2} with target 0 → Expected result: 4
2. Target not present: Same array with target 3 → Expected result: -1
3. Array with duplicates: {2, 2, 2, 3, 4, 2} with target 3 → Expected result: 3
4. Unrotated array: {1, 2, 3, 4, 5} with target 3 → Expected result: 2
5. Single element: {5} with target 5 → Expected result: 0
6. Two elements: {2, 1} with target 2 → Expected result: 0
7. Empty array: {} with target 1 → Expected result: -1
8. Target at beginning: {3, 1, 2} with target 3 → Expected result: 0
9. Target at end: {3, 1, 2} with target 2 → Expected result: 2

Tricky Cases:

• Arrays with duplicate elements require special handling in binary search
• Edge cases involving single or two-element arrays
• Unrotated arrays (which are just a special case of rotated arrays)

Boundary Cases:

• Empty input arrays
• Arrays with only one or two elements
• Target values at array boundaries (first/last positions)
• Arrays where rotation point is at the beginning or end

11. Final Summary

The core idea is to leverage binary search's divide-and-conquer nature by identifying which half of the rotated array is properly sorted, then determining if the target lies within that sorted range to eliminate half the search space at each step. This solution works because rotation creates a unique property where at least one half is always sorted, enabling efficient pruning of search space. The algorithm achieves optimal O(log n) time complexity by maintaining the invariant that we only explore portions of the array where the target could possibly exist, making it highly efficient for large datasets.