Search in Rotated Sorted Array — Pivot-Aware Binary Search
Decide which side of the pivot is sorted at every step so the binary search converges on the target in logarithmic time.
Problem Statement
You are given an ascending array that has been rotated at an unknown pivot. Search for target and return its index, or -1 if it is absent.
Why This Problem Matters
- Forces you to reason about invariants instead of relying on a memorised binary search template.
- Highlights how partial ordering can still yield logarithmic search time.
- Common follow-up to the “find minimum” variant, so interviewers expect the pattern pivot.
Thought Process
Identify sorted half each iteration
Compare nums[left] and nums[mid]. If nums[left] <= nums[mid], the left half is sorted; otherwise the right half is sorted.
Check if target falls inside the sorted region
Only continue searching where the target could possibly exist. If the target is within the sorted half, discard the other side.
Shrink the search space aggressively
Adjust left and right pointers exactly like normal binary search once you know which half to keep.
Step-by-Step Reasoning
- Initialise left = 0 and right = nums.length - 1.
- While left <= right, compute mid = left + (right - left) / 2.
- If nums[mid] equals target, return mid.
- Decide which half is sorted and move pointers accordingly; continue until the range collapses.
Dry Run
nums = [4,5,6,7,0,1,2], target = 0
Left half sorted but target not inside → search right half; converge on index 4.
nums = [4,5,6,7,0,1,2], target = 3
Target never found, pointers cross, return -1.
Complexity Analysis
Time
O(log n)
Space
O(1)
Why
Binary search halves the search interval each loop without additional storage.
Annotated Solution
public class SearchInRotatedSortedArray {
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;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}Deciding which half is sorted determines where the target might live. Once the incorrect half is discarded the loop behaves like classic binary search.
Common Pitfalls
- Using strict < comparisons incorrectly when checking sorted halves can skip valid answers.
- Forgetting to include equality in the range test excludes endpoints and returns -1 incorrectly.
- Neglecting overflow-safe midpoint calculation may break very large arrays.
Follow-Up Questions
- How would you change the logic if the array contained duplicates?
- Can you extend the method to return the count of occurrences instead of an index?