Search in Rotated Sorted Array
Mahabharata — The Rotated Formation — Finding a Specific Warrior After the Army Shifted
भ्रमित व्यवस्था में — लक्ष्य कहाँ?। आधा व्यवस्थित — तत्र खोजो सत्य॥
*In a rotated order — where is the target? One half is always sorted — seek the truth there.*
The Story
A sorted array rotated at an unknown pivot. Find the target's index, or return -1.
For `nums = [4,5,6,7,0,1,2]`, target=0: return 4. For `nums = [4,5,6,7,0,1,2]`, target=3: return -1.
**Key insight:** In any mid position of a rotated array, ONE of the two halves is always sorted. - If `nums[left] <= nums[mid]`: the LEFT half [left..mid] is sorted - Otherwise: the RIGHT half [mid..right] is sorted
Once we identify the sorted half, we check if target lies within it. If yes → search that half. If no → search the other half.
```java while (left <= right) { int mid = left+(right-left)/2; if (nums[mid] == target) return mid; if (nums[left] <= nums[mid]) { // Left half sorted if (nums[left] <= target && target < nums[mid]) right = mid-1; else left = mid+1; } else { // Right half sorted if (nums[mid] < target && target <= nums[right]) left = mid+1; else right = mid-1; } } ```
Trace `[4,5,6,7,0,1,2]`, target=0: - l=0,r=6,mid=3,nums[3]=7≠0. nums[0]=4<=nums[3]=7 (left sorted). target=0 not in [4,7] → left=4 - l=4,r=6,mid=5,nums[5]=1≠0. nums[4]=0<=nums[5]=1 (left sorted). 0 in [0,1]? 0<=0<1 → yes → right=4 - l=4,r=4,mid=4,nums[4]=0==0 → return 4 ✓
The Linear Target Finder
Scan from left for target. O(n).
public int searchBruteForce(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
if (nums[i] == target) return i;
return -1;
}The Sorted-Half Wisdom
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) { // Left half is sorted
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else { // Right half is sorted
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}Step-by-Step Walkthrough
[3,1], target=1 l=0,r=1,mid=0,nums[0]=3≠1 nums[0]=3<=nums[0]=3 (left sorted, only one element). 3<=1<3? No → left=1 l=1,r=1,mid=1,nums[1]=1==1 → return 1 ✅
Deep Insight
**The sorted-half guarantee:** In any rotated sorted array, when you split at mid, at least one half is a contiguous sorted segment. This is the crucial property that makes binary search viable.
**`nums[left] <= nums[mid]` uses `<=`** to handle the case where left==mid (single element): a single-element range is trivially sorted.
**Target range check:** For sorted left half [left..mid], target must satisfy `nums[left] <= target < nums[mid]` (strictly less than mid, since we already checked nums[mid] != target). Similar logic for right half.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Linear scan |
| Optimal | O(log n) | O(1) | Binary search exploiting one-always-sorted-half property |
Pattern Recognition
✅ Rotated sorted array — find target ✅ One half always sorted; check which ✅ If target in sorted range: search there; else other half ✅ Return -1 if not found **LeetCode Trigger Phrases:** → "search in rotated sorted array" → "find target in rotated array" → Two-case binary search on rotated structure
Bhagavad Gita 8.7
तस्मात्सर्वेषु कालेषु मामनुस्मर युध्य च। मय्यर्पितमनोबुद्धिर्मामेवैष्यस्यसंशयः॥
Therefore, at all times remember Me and fight. With mind and intellect surrendered to Me, you will come to Me alone — there is no doubt.
Connection: In the rotated formation, certainty (one sorted half) always exists even amid apparent disorder. The algorithm finds this certitude at every step: though the whole array seems disorganized, one half is always reliably ordered. Like Krishna's promise that surrender to the divine always provides clear direction even in the chaos of battle, the algorithm always identifies the reliable half and searches it with confidence.