How to Solve Search in Rotated Sorted Array on LeetCode
The Search in Rotated Sorted Array problem tests your knowledge of modified binary search.
Problem Statement
Given an integer array nums sorted in ascending order, rotated at an unknown pivot, and a target value, return the index of target if it is in nums, or -1 if it is not. Must run in O(log n) time.
Example:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Why This Problem Matters for Interviews
- Combines array, binary search, and edge case handling
- Common in big tech interviews
- Useful for understanding search algorithms in non-standard arrays
Approach to Search in Rotated Sorted Array
Modified Binary Search (Optimal)
Identify which half is sorted and decide which side to search.
Time Complexity: O(log n)
Space Complexity: O(1)
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]: # left half is sorted
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
Key Interview Talking Points
- Why binary search still works
- Identifying sorted halves
- Handling duplicates (follow-up)
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search | O(log n) | O(1) |
Pro Interview Tips
- Draw rotated arrays and pivots
- Explain each binary search step
- Handle single-element and empty arrays