Problem Statement
Given a rotated sorted array nums and an integer target, return the index of target.
If the target does not exist, return -1.
You must solve it in:
O(log N)
time.
Brute Force Intuition
In an interview, you can explain it like this:
We can scan the array from left to right and compare every element with the target. As soon as we find the target, we return its index. This works but does not utilize the sorted nature of the array.
Complexity
- Time Complexity: O(N)
- Space Complexity: O(1)
Brute Force Code
class Solution {
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target)
return i;
}
return -1;
}
}
Moving Towards the Optimal Approach
A normal Binary Search works only when the array is completely sorted.
But after rotation:
[4,5,6,7,0,1,2]
the entire array is not sorted.
However, one important property still remains:
At least one half is always sorted.
This observation allows us to eliminate half of the search space every time.
Pattern Recognition
Whenever you see:
- Sorted Array
- Rotation
- Search Target
Think:
Modified Binary Search
Key Observation
For any mid:
[4,5,6 | 7 | 0,1,2]
One side will always be sorted.
Either:
Left Half Sorted
or
Right Half Sorted
Once we identify the sorted half, we check whether the target lies inside it.
Optimal Approach
Case 1
Left Half Sorted
if(nums[low] <= nums[mid])
Example:
4 5 6 7
If target lies within:
nums[low] <= target < nums[mid]
Search left.
Otherwise search right.
Case 2
Right Half Sorted
else
Example:
0 1 2
If target lies within:
nums[mid] < target <= nums[high]
Search right.
Otherwise search left.
Optimal Java Solution
class Solution {
public int search(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid;
if (arr[low] <= arr[mid]) {
if (arr[low] <= target &&
target < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
if (arr[mid] < target &&
target <= arr[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
}
}
Dry Run
Input
nums = [4,5,6,7,0,1,2]
target = 0
Iteration 1
low = 0
high = 6
mid = 3
nums[mid] = 7
Left side:
4 5 6 7
is sorted.
Check:
0 lies between 4 and 7 ?
No.
Move Right.
low = 4
Iteration 2
low = 4
high = 6
mid = 5
nums[mid] = 1
Left side:
0 1
is sorted.
Check:
0 lies between 0 and 1 ?
Yes.
Move Left.
high = 4
Iteration 3
low = 4
high = 4
mid = 4
nums[mid] = 0
Found Target ✅
Answer = 4
Why This Works?
Even though the array is rotated:
One half always remains sorted.
Using that sorted half, we can determine whether the target can exist there.
This allows us to eliminate half the search space every iteration.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(log N) |
| Space Complexity | O(1) |
Interview One-Liner
In a rotated sorted array, at least one half is always sorted. Identify the sorted half and decide whether the target lies inside it to eliminate half the search space.
Pattern Learned
Sorted Array
+
Rotation
+
Search
=> Modified Binary Search
Similar Problems
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Single Element in Sorted Array
- Peak Element
Memory Trick
Think:
Find Sorted Half
↓
Target Inside ?
↓
Yes → Go There
No → Go Other Half
Mental Model
Normal Binary Search
→ Array Fully Sorted
Rotated Binary Search
→ One Half Sorted
Whenever you hear:
"Search in Rotated Sorted Array"
your brain should immediately think:
Find Sorted Half → Check Target Range → Eliminate Half