Problem Description

You are given an integer array nums that was originally sorted in ascending order with all distinct values. However, this array may have been left rotated at some unknown pivot index k (where 1 <= k < nums.length).

A left rotation at index k means the array is rearranged from its original order [nums[0], nums[1], ..., nums[n-1]] to [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

For example:

• Original sorted array: [0,1,2,4,5,6,7]
• After left rotation by 3 indices: [4,5,6,7,0,1,2]

Your task is to search for a given target value in this possibly rotated array and return its index. If the target is not found in the array, return -1.

Key Requirements:

• The algorithm must have O(log n) runtime complexity
• The array contains distinct values (no duplicates)
• The array may or may not be rotated

The challenge is to efficiently search in this rotated sorted array without first finding the rotation point or restoring the original order. Since the required time complexity is O(log n), a linear search is not acceptable - you need to use a modified binary search approach that can handle the rotation.

Intuition

When we look at a rotated sorted array, we notice an important property: if we split the array at any point, at least one half will always be properly sorted. This is the key insight that allows us to use binary search even though the entire array isn't sorted.

Let's understand why this works. Consider the array [4,5,6,7,0,1,2]:

• If we pick the middle element (index 3, value 7), we can check:
  • Left half: [4,5,6,7] - this is sorted (4 ≤ 5 ≤ 6 ≤ 7)
  • Right half: [7,0,1,2] - this is not sorted (7 > 0)

The magic happens because we can easily identify which half is sorted by comparing the first and last elements of that half. If nums[left] <= nums[mid], then the left half is sorted. Otherwise, the right half must be sorted.

Once we know which half is sorted, we can make an intelligent decision about where to search next:

• If the sorted half contains our target (we can check this easily since it's sorted), we search there
• Otherwise, the target must be in the unsorted half (if it exists at all)

This approach works because:

1. We can always identify at least one sorted portion
2. In a sorted portion, we can definitively determine if the target lies within its range by checking the boundaries
3. This allows us to eliminate half of the search space in each iteration, maintaining O(log n) complexity

The beauty of this solution is that we don't need to find the rotation point first. We simply adapt our binary search to handle both the sorted and rotated portions dynamically as we encounter them.

Learn more about Binary Search patterns.

Solution Approach

We use a direct binary search approach. At each step, we check if nums[mid] is the target. If not, we determine which half is sorted and decide where to search next.

Algorithm Steps:

1. Check for match: If nums[mid] == target, return mid immediately.

2. Determine which half is sorted: Compare nums[left] with nums[mid].

   • If nums[left] <= nums[mid], the left half [left, mid] is sorted.
   • Otherwise, the right half [mid, right] is sorted.

3. Decide where to search:

   • If the left half is sorted and nums[left] <= target < nums[mid], search left.
   • If the right half is sorted and nums[mid] < target <= nums[right], search right.
   • Otherwise, search the other half.

Why This Works:

In a rotated sorted array, at least one half is always properly sorted. For the sorted half, we can easily check if the target lies within its range by comparing boundary values. If the target is in the sorted range, we search there. Otherwise, the target must be in the unsorted half (if it exists).

Time Complexity: O(log n) - we eliminate half of the search space in each iteration Space Complexity: O(1) - only using a constant amount of extra space for pointers

Example Walkthrough

Let's trace through the algorithm with array [4,5,6,7,0,1,2] searching for target = 0.

Initial State:

• Array: [4,5,6,7,0,1,2] (indices 0-6)
• left = 0, right = 6, target = 0

Iteration 1:

• Calculate mid = (0 + 6) // 2 = 3
• nums[mid] = 7, not equal to target 0
• Check if left half is sorted: nums[0] = 4 <= nums[3] = 7 ✓
• Is target in sorted left half? Check if 4 <= 0 < 7: No (0 < 4)
• Target not in left half → search right: left = mid + 1 = 4

Iteration 2:

• left = 4, right = 6
• Calculate mid = (4 + 6) // 2 = 5
• nums[mid] = 1, not equal to target 0
• Check if left half is sorted: nums[4] = 0 <= nums[5] = 1 ✓
• Is target in sorted left half? Check if 0 <= 0 < 1: Yes!
• Target in left half → search left: right = mid - 1 = 4

Iteration 3:

• left = 4, right = 4
• Calculate mid = (4 + 4) // 2 = 4
• nums[mid] = 0, equal to target 0 ✓
• Return 4

The algorithm successfully finds the target at index 4 in just 3 iterations, demonstrating O(log n) efficiency.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n), where n is the length of the array nums. In each iteration, the search space is reduced by half (either updating left = mid + 1 or right = mid - 1), which results in at most log₂(n) iterations.

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for the variables left, right, and mid, regardless of the input size. No additional data structures or recursive calls are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Check for Target Match First

The Pitfall: Jumping directly into determining which half is sorted without first checking if nums[mid] == target.

Example of the Issue:

while left <= right:
    mid = (left + right) // 2
    # Forgot to check nums[mid] == target!
    if nums[left] <= nums[mid]:
        ...

Solution: Always check for target match first:

if nums[mid] == target:
    return mid

2. Incorrect Boundary Comparison When Determining the Sorted Half

The Pitfall: Using strict inequality (nums[left] < nums[mid]) instead of nums[left] <= nums[mid] when determining which half is sorted.

Example of the Issue:

if nums[left] < nums[mid]:  # Wrong! Missing the equal case
    # Left half logic

Consider the array [3, 1] searching for target 1:

• With strict inequality: 3 < 3 is false, incorrectly assuming right half is sorted
• With correct comparison: 3 <= 3 is true, correctly identifying left half pattern

Solution: Always use <= to properly handle all cases:

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

3. Off-by-One Errors in Range Checks

The Pitfall: Using incorrect comparison operators when checking if target is in the sorted range.

Example of the Issue:

# Wrong: includes mid in the range check
if nums[left] <= target <= nums[mid]:
    right = mid - 1

Since we already checked nums[mid] != target, including nums[mid] in the range means the condition is never satisfied when target == nums[mid].

Solution: Use exclusive comparison for nums[mid]:

# Left half sorted: target must be >= left and < mid
if nums[left] <= target < nums[mid]:
    right = mid - 1

# Right half sorted: target must be > mid and <= right
if nums[mid] < target <= nums[right]:
    left = mid + 1

4. Confusing Which Half to Search

The Pitfall: Searching the wrong half when the target is not in the sorted range.

Example of the Issue:

if nums[left] <= nums[mid]:
    if nums[left] <= target < nums[mid]:
        right = mid - 1
    # Forgot else case - infinite loop!

Solution: Always handle both cases for each sorted half:

if nums[left] <= nums[mid]:
    if nums[left] <= target < nums[mid]:
        right = mid - 1
    else:
        left = mid + 1  # Target must be in the other half