A rotated sorted array was originally sorted but shifted at some pivot:
[1, 2, 3, 4, 5, 6]
↓ rotate
[4, 5, 6, 1, 2, 3]The key observation:
At least one half of the array is always sorted.
Focus on recognizing:
Rotated → find the sorted half → decide which half can contain the target
Pattern 1: Search in Rotated Sorted Array
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Search in Rotated Sorted Array
Search a rotated sorted array in O(log n). At each mid, one half is guaranteed sorted — check which side the target falls in.
Array: [4,5,6,7,0,1,2], target=0. Left half [4,5,6,7] is sorted. 0 < 4 → search right half.
1
lo = 0, hi = n - 1
2
while lo <= hi:
3
mid = (lo + hi) / 2
4
if nums[mid] == target: return mid
5
left sorted? if yes: check if target in left range
6
else: right sorted — check if target in right range
public int search(int[] nums, int target) {
int lo = 0;
int hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[lo] <= nums[mid]) {
// left half is sorted
if (target >= nums[lo] && target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
// right half is sorted
if (target > nums[mid] && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;
}def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
# left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1int search(vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) {
// left half is sorted
if (target >= nums[lo] && target < nums[mid])
hi = mid - 1;
else
lo = mid + 1;
} else {
// right half is sorted
if (target > nums[mid] && target <= nums[hi])
lo = mid + 1;
else
hi = mid - 1;
}
}
return -1;
}function search(nums, target) {
let lo = 0,
hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) {
// left half is sorted
if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
// right half is sorted
if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}Two questions per step: which half is sorted? (
nums[lo] <= nums[mid]→ left), then is the target inside it?
Pattern 2: Find Minimum
Watch [4,5,6,1,2,3] shrink to its minimum in three probes — every step keeps the minimum inside [lo..hi]. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Minimum in a Rotated Sorted Array
Find the smallest element in a rotated sorted array in O(log n) using binary search. The key insight: the pivot (minimum) is always in the unsorted half of the current range.
Array [4,5,6,1,2,3] was sorted then rotated. Compare mid (6) with the right end (3): if mid > right, the minimum is to the RIGHT of mid (a rotation happened there), so lo = mid+1; otherwise it's to the left or at mid, so hi = mid. The L/R pointers track the live range and we land on the minimum 1.
1
lo = 0, hi = n - 1
2
while lo < hi:
3
mid = (lo + hi) / 2
4
if nums[mid] > nums[hi]: // break is RIGHT of mid
5
lo = mid + 1
6
else: // right half sorted →
7
hi = mid // min is at mid or left of it
8
return nums[lo]
1
while lo <= hi:
2
mid = (lo + hi) / 2
3
if nums[mid] == target: return mid
4
if nums[lo] <= nums[mid]: // LEFT half sorted?
5
if nums[lo] <= target < nums[mid]:
6
hi = mid - 1 // target inside it
7
else: lo = mid + 1
8
else: // RIGHT half sorted…
9
… symmetric check on the right
The minimum sits exactly where the rotation begins:
public int findMin(int[] nums) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) {
lo = mid + 1; // drop is right of mid
} else {
hi = mid; // min at mid or left of it
}
}
return nums[lo];
}def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # drop is right of mid
else:
hi = mid # min at mid or left of it
return nums[lo]int findMin(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi])
lo = mid + 1; // drop is right of mid
else
hi = mid; // min at mid or left of it
}
return nums[lo];
}function findMin(nums) {
let lo = 0,
hi = nums.length - 1;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] > nums[hi]) lo = mid + 1;
// drop is right of mid
else hi = mid; // min at mid or left of it
}
return nums[lo];
}Find Min = compare
midwithhi.nums[mid] > nums[hi]means the drop — and the minimum — live strictly right.
Variant: Duplicates
When nums[lo] == nums[mid] == nums[hi], neither half is provably sorted. Shrink both ends:
lo++; hi--;Worst case degrades to O(n) — unavoidable with heavy duplication.
Common Mistakes
Skipping the sorted-half check.
Deciding where the target lives before knowing which half is sorted is guessing.
Wrong target-range comparisons.
Sorted left: target >= nums[lo] && target < nums[mid]. Sorted right: target > nums[mid] && target <= nums[hi]. Note the asymmetric bounds.
Using lo <= hi for find-min.
The minimum template converges with while (lo < hi) and answers at lo == hi.
Complexity
| Operation | Time |
|---|---|
| Search | O(log n) |
| Find min | O(log n) |
| With duplicates | O(n) worst |
Premium Content
Unlock Binary Search in Rotated Array and all premium lessons with a subscription.
From ₹199.99/year — See plans