8 / 75
Medium
Search in Rotated Sorted Array
#8arraybinary-search
Identify which half is sorted, then determine if target lies in that sorted half to decide search direction.
Example:
Input:
nums = [4,5,6,7,0,1,2], target = 0Output:
4 (target 0 is found at index 4)Common Mistakes:
- Not handling the case where left side is sorted vs. right side is sorted separately
- Using strict inequality when comparing boundaries (should be <= for left boundary)
- Forgetting that one half is always guaranteed to be sorted
Notes:
All values are unique. Key insight: at least one half is always sorted. Use that sorted half to determine if target is in range, then search accordingly.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Identify which half is sorted, then determine if target lies in that sorted half to decide search direction.
Example:
Input:
nums = [4,5,6,7,0,1,2], target = 0Output:
4 (target 0 is found at index 4)Common Mistakes:
- Not handling the case where left side is sorted vs. right side is sorted separately
- Using strict inequality when comparing boundaries (should be <= for left boundary)
- Forgetting that one half is always guaranteed to be sorted
Notes:
All values are unique. Key insight: at least one half is always sorted. Use that sorted half to determine if target is in range, then search accordingly.
8/75
Search in Rotated Sorted Array