Search in a Rotated Sorted Array
- Jan 17
- 4 min read
The "Search in a Rotated Sorted Array" is deceptively simple at first glance. It smells like binary search, but with a twist that forces you to reason carefully about sorted segments. It’s a great test of whether you truly understand binary search or are just memorizing it.
Problem Statement
You are given an integer array nums that was originally sorted in ascending order, but then rotated at some unknown pivot. You are also given a target value.
Your task is to return the index of the target if it exists in the array, or -1 if it does not.
Example:
nums = [1,2,3,4,5,6,7,8,0]
target = 0
Output: 4
1. Clarify Requirements Before Jumping Into Code
I want to confirm a few things before diving in:
The array contains distinct integers
The array is guaranteed to be rotated once (or possibly not rotated at all)
If the target does not exist, I return -1
While the problem could be solved by a linear scan, we should assume we can solve it logarithmic time
2. Identify the Category of the Question
This sounds like a search problem. Since the sorting properties change at a pivot, it's likely a problem that could be solved with a modified of Binary Search.
We'll need to think through how to reason about the sorted halves of the array and how to make comparisons that are pivot-aware.
3. Consider a Brute-Force Approach to Understand the Problem
The simplest thing I could do is scan through the array and return the index if I see the target.
That would work, but it runs in O(n) time, which is insufficient.
Still, it confirms that the problem is just search — the complexity requirement is the real challenge.
4. Brainstorm More Solutions
So, let's think through how to adapt binary search to a rotated array.
My first thought is: can we find the pivot first? If we locate the smallest element using binary search, that gives me the rotation index. Once we know that:
I know what index I could use if I wanted to split my array into two sorted halves
I could decide which half the target belongs to
And then I can run binary search on just that half
But then the question, how do I find the pivot? A linear scan gives me a solution with O(n) time, which we have already decided to optimize on. Not to mention, if I already know how to optimally find the pivot, why not simply apply that same logic to find the target directly instead of adding unnecessary logic to find the pivot first?
So, is there a way to solve this without having to explicitly find the pivot?
If I don't know the pivot, I can't go directly to that index where I will know that I have two sorted halves on either side of the pivot.
Is there anything I do know about the two halves an array when I pick a midpoint?
There is, actually! I know that at least one side of the array on either side of my midpoint must be sorted. And if I know which half of my array is sorted, then I can pretty easily identify whether or not my target is in that sorted half.
If my target is in the sorted half of the array, I continue my binary search algorithm on that half.
And if my target is not in the sorted half of the array, then I continue my binary search with the unsorted half.
How do I know which side of the array is sorted? Let's think about what I know about the unsorted half of the array - it is unsorted because of the pivot. The pivot creates a scenario where the left-most element should be larger than the right-most element. I can use that logic to decide which half is sorted - the sorted half is the one where my left-most element is smaller than the right-most element.
This keeps everything in one binary search loop with O(log n) time, which is optimal.
5. Discuss Trade-Offs Between Your Solutions
Approach | Time | Space | Pros | Cons |
Linear Scan | O(n) | O(1) | Simple | Too slow |
Find Pivot + Binary Search | O(log n) | O(1) | Clear separation of steps | More logic |
Modified Binary Search | O(log n) | O(1) | Clean, single pass | Requires careful reasoning |
6. Optimal Solution Recap
The optimal approach is a modified binary search:
Maintain left and right pointers
At each step:
Identify which half is sorted
Decide whether the target lies in that half
Narrow the search space accordingly
Stop when the target is found or the window closes
7. Write Pseudocode to Structure Your Thoughts
left = 0, right = n - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target: return mid
if left half is sorted:
if target in left half:
right = mid - 1
else:
left = mid + 1
else:
if target in right half:
left = mid + 1
else:
right = mid - 1
return -1
8. Consider Edge Cases
Array not rotated at all
Target equals first or last element
Single-element array
Target does not exist
Very small arrays (size 1 or 2)
9. Write Full Code Syntax (Java)
public class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// Left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}
10. Test Your Code
System.out.println(new Solution().search(
new int[]{4,5,6,7,0,1,2}, 0)); // 4
System.out.println(new Solution().search(
new int[]{4,5,6,7,0,1,2}, 3)); // -1
System.out.println(new Solution().search(
new int[]{1}, 1)); // 0
System.out.println(new Solution().search(
new int[]{1,3}, 3)); // 1
System.out.println(new Solution().search(
new int[]{5,1,3}, 5)); // 0
11. Key Lessons to Remember for Future Questions
Binary search is about eliminating half the search space, which is logic you can theoretically apply to at least some types of unsorted array
In rotated arrays, one side is always sorted
Asking the right comparison questions is more important than memorizing code
This pattern shows up again in rotated arrays with duplicates and pivot problems
Comments