Algorithm

Search in Rotated Sorted Array

Binary Search Pattern

Search in Rotated Sorted Array

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

CONSTRAINTS
  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i], target <= 10^4
  • All values of nums are unique
EXAMPLE 1
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
EXAMPLE 2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Is it possible for the target to be in both halves?
No. Since all values are unique and the array was originally sorted, the target can exist at most once in the entire array.

Searching for a target in a rotated array is tricky because the "sorted order" is broken by a rotation point.

The Linear Escape

You could just scan every element (O(N)). But for large inputs, we want the logarithmic efficiency of Binary Search. The problem is: how do we binary search if the array isn't perfectly sorted?

The "Clean Segment" Discovery

Discover: No matter where you pick a midpoint in a rotated sorted array, at least one half is always perfectly sorted.

1. Identify the Sorted Half: Compare the Left pointer to the Midpoint. If Left <= Mid, the left half is the "clean" segment. Otherwise, the right half must be the "clean" one.
2. Check the Bounds: If your target falls within the value range of the clean segment, you can discard the other half and focus there.
3. Pivot: If the target isn't in the clean segment, it must be in the "messy" segment. Jump into the mess and repeat.
Code Blueprint
text
left = 0
right = length - 1

WHILE left <= right:
    mid = left + (right - left) / 2
    
    IF nums[mid] == target: RETURN mid
    
    // Identify which half is "Clean" (Sorted)
    IF nums[left] <= nums[mid]:
        // Left half is clean
        IF target >= nums[left] AND target < nums[mid]:
            right = mid - 1 // Target is in the clean left half
        ELSE:
            left = mid + 1  // Target is in the messy right half
    ELSE:
        // Right half is clean
        IF target > nums[mid] AND target <= nums[right]:
            left = mid + 1  // Target is in the clean right half
        ELSE:
            right = mid - 1 // Target is in the messy left half

RETURN -1
Why the Pattern is King

Search in Rotated Array is the ultimate test of "Decision Logic." Binary Search works not because the data is perfectly ordered, but because we can definitively eliminate half the search space based on a single condition. By identifying the "clean" half of the rotation, we maintain O(log N) speed even in a fragmented landscape.

Interactive Strategy Visualization

Search in Rotated Array

One half of the array is always sorted. Identify the sorted half, then check if the target lies within its range.

Target0
4Left
5
6
7
0
1
2Right
🔄
Locating Middle...

O(N) linear scan
→
O(log N) binary search