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 implement a modified binary search that handles the rotation by identifying which half of the current search range is sorted.

Algorithm Steps:

1. Initialize pointers: Set left = 0 and right = n - 1 to define our search boundaries.

2. Binary search loop: While left < right:

   • Calculate the middle index: mid = (left + right) >> 1 (using bit shift for division by 2)
   • Determine which half is sorted by checking if nums[0] <= nums[mid]

3. Case 1: Left half is sorted (nums[0] <= nums[mid]):

   • The range [0...mid] forms a sorted array
   • Check if target is within this sorted range: nums[0] <= target <= nums[mid]
   • If yes, narrow search to left half: right = mid
   • If no, target must be in right half: left = mid + 1

4. Case 2: Right half is sorted (when left half is not sorted):

   • The range [mid+1...n-1] must be sorted
   • Check if target is within this sorted range: nums[mid] < target <= nums[n-1]
   • If yes, narrow search to right half: left = mid + 1
   • If no, target must be in left half: right = mid

5. Final check: After the loop terminates (when left >= right):

   • Check if nums[left] == target
   • Return left if match found, otherwise return -1

Key Implementation Details:

• We use right = mid instead of right = mid - 1 in some cases because our target might be at mid position
• The condition nums[0] <= nums[mid] effectively tells us if the rotation point is in the right half
• We compare with nums[0] and nums[n-1] to determine the boundaries of sorted portions
• The bit shift operation >> 1 is used for efficient division by 2

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) >> 1 = 3
• nums[mid] = 7
• Check if left half is sorted: nums[0] = 4 <= nums[3] = 7 ✓ (left half [4,5,6,7] is sorted)
• Is target in sorted left half? Check if 4 <= 0 <= 7
  • No, because 0 < 4
• Target must be in right half, so set left = mid + 1 = 4

Iteration 2:

• Current search range: indices 4-6 → [0,1,2]
• left = 4, right = 6
• Calculate mid = (4 + 6) >> 1 = 5
• nums[mid] = 1
• Check if left half is sorted: nums[0] = 4 <= nums[5] = 1? No (comparing with original nums[0])
• Since left half is not sorted, right half must be sorted
• Check if target is in sorted right half: nums[5] = 1 < 0 <= nums[6] = 2?
  • No, because 0 < 1
• Target must be in left half, so set right = mid = 5

Iteration 3:

• Current search range: indices 4-5 → [0,1]
• left = 4, right = 5
• Calculate mid = (4 + 5) >> 1 = 4
• nums[mid] = 0
• Check if left half is sorted: nums[0] = 4 <= nums[4] = 0? No
• Since left half is not sorted, right half must be sorted
• Check if target is in sorted right half: nums[4] = 0 < 0 <= nums[6] = 2?
  • No, because 0 = 0 (not strictly greater)
• Target must be in left half, so set right = mid = 4

Iteration 4:

• left = 4, right = 4
• Loop condition left < right is false, exit loop

Final Check:

• nums[left] = nums[4] = 0
• Does nums[4] == target? Yes, 0 == 0 ✓
• Return 4

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

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n), where n is the length of the array nums. The algorithm uses binary search to find the target element in a rotated sorted array. In each iteration of the while loop, the search space is reduced by half (either updating left = mid + 1 or right = mid), 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 n, left, right, and mid, regardless of the input size. No additional data structures or recursive calls are used that would scale with the input size.

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

Common Pitfalls

1. Incorrect Boundary Comparison When Determining the Sorted Half

The Pitfall: A common mistake is using strict inequality (nums[0] < nums[mid]) instead of nums[0] <= nums[mid] when determining which half is sorted. This causes incorrect behavior when nums[0] == nums[mid], which can happen in small arrays or specific rotation scenarios.

Example of the Issue:

# Incorrect implementation
if nums[0] < 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[0] <= nums[mid]:  # Correct
    # Left half is sorted or entire array from 0 to mid is sorted

2. Off-by-One Errors in Range Checking

The Pitfall: When checking if the target falls within a sorted range, developers often make boundary errors by excluding valid endpoints or using incorrect comparison operators.

Example of the Issue:

# Incorrect: Missing boundary values
if nums[0] < target < nums[mid]:  # Wrong! Excludes valid endpoints
    right = mid

# Another mistake: Incorrect boundary for right half
if nums[mid] <= target <= nums[n - 1]:  # Wrong! Would include mid twice
    left = mid + 1

Solution: Use inclusive comparisons for the sorted range boundaries:

# For left sorted half:
if nums[0] <= target <= nums[mid]:
    right = mid  # Include mid since target could equal nums[mid]

# For right sorted half:
if nums[mid] < target <= nums[n - 1]:  # Exclude mid since we already checked it
    left = mid + 1

3. Inconsistent Mid-Point Updates

The Pitfall: Mixing right = mid - 1 and right = mid patterns inconsistently, or using left = mid without adding 1, leading to infinite loops.

Example of the Issue:

# This can cause infinite loop
while left < right:
    mid = (left + right) >> 1
    # ... some conditions ...
    left = mid  # Dangerous! Can cause infinite loop when left = right - 1

Solution: Be consistent with the update pattern:

• When moving left pointer: always use left = mid + 1
• When moving right pointer: use right = mid (since we might need to include mid in search)
• Ensure the loop condition matches the update pattern (while left < right with this approach)

4. Forgetting to Handle Edge Cases

The Pitfall: Not properly handling arrays with only 1 or 2 elements, or not checking if the final position contains the target.

Example of the Issue:

# Forgetting final check
while left < right:
    # ... binary search logic ...
  
return -1  # Wrong! Didn't check if nums[left] == target

Solution: Always validate the final position after the loop:

return left if nums[left] == target else -1

Also ensure the algorithm works for minimal cases:

• Single element: [1] searching for 1 or 0
• Two elements: [2, 1] with various targets
• Non-rotated array: [1, 2, 3, 4, 5]