63. Find Minimum in Rotated Sorted Array
🔗 LeetCode Problem: 153. Find Minimum in Rotated Sorted Array
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search
Problem Statement
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2]if it was rotated4times.[0,1,2,4,5,6,7]if it was rotated7times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was not rotated.
Constraints:
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All the integers of nums are unique
- nums is sorted and rotated between 1 and n times
🎨 Visual Understanding
The Problem Visualized
Original sorted array:
[0, 1, 2, 4, 5, 6, 7]
↑
min
Rotated 4 times:
[4, 5, 6, 7, 0, 1, 2]
↑
min (at rotation point!)
Key observation:
The MINIMUM is at the ROTATION POINT!
Visual patterns:
[4, 5, 6, 7, 0, 1, 2]
↑→→→→ drop! ←←←↑
The "drop" is where rotation happened
The minimum is where the drop occurs!
Different rotation scenarios:
No rotation (sorted):
[1, 2, 3, 4, 5, 6, 7]
↑
min at index 0
Rotated once:
[7, 1, 2, 3, 4, 5, 6]
↑
min
Rotated multiple times:
[4, 5, 6, 7, 0, 1, 2]
↑
min
🚨 CRITICAL INSIGHT - Compare with Right Boundary!
The Key Pattern!
In a rotated sorted array:
There's a "break point" where larger values → smaller values
This break point is where the MINIMUM is!
How to find it?
Compare MIDDLE with RIGHT boundary!
If nums[mid] > nums[right]:
Minimum is in RIGHT half
(there's a rotation point to the right)
If nums[mid] < nums[right]:
Minimum is in LEFT half or IS mid
(mid could be the minimum)
Why compare with RIGHT, not LEFT? (CRITICAL!)
═══════════════════════════════════════════════════════════════
Let's compare BOTH approaches to understand:
WRONG: Comparing with LEFT
────────────────────────────────────────────────────────────
Example 1: [4, 5, 6, 7, 0, 1, 2]
↑ ↑ ↑
left mid right
Compare nums[mid] with nums[left]:
nums[mid] = 7, nums[left] = 4
7 > 4 (mid greater than left)
What does this tell us?
Left side [4,5,6,7] is sorted
But where is the MINIMUM?
- Is it at left (4)?
- Is it on the right (0)?
We CAN'T DECIDE! AMBIGUOUS! ✗
Example 2: [0, 1, 2, 4, 5, 6, 7] (no rotation)
↑ ↑ ↑
left mid right
Compare nums[mid] with nums[left]:
nums[mid] = 4, nums[left] = 0
4 > 0 (mid greater than left)
Same comparison result (mid > left) but:
Minimum is at LEFT in this case!
Same comparison → Different answers = AMBIGUOUS! ✗
CORRECT: Comparing with RIGHT
────────────────────────────────────────────────────────────
Example 1: [4, 5, 6, 7, 0, 1, 2]
↑ ↑ ↑
left mid right
Compare nums[mid] with nums[right]:
nums[mid] = 7, nums[right] = 2
7 > 2 (mid greater than right)
What does this tell us?
There's a DROP between mid and right!
[7 ... 0, 1, 2] - values decrease
Minimum MUST be to the RIGHT!
CLEAR DECISION! ✓
Example 2: [0, 1, 2, 4, 5, 6, 7] (no rotation)
↑ ↑ ↑
left mid right
Compare nums[mid] with nums[right]:
nums[mid] = 4, nums[right] = 7
4 < 7 (mid less than right)
What does this tell us?
Right side [4,5,6,7] is sorted
No drop on right, so drop must be on LEFT or mid IS minimum
CLEAR DECISION! ✓
THE KEY INSIGHT:
────────────────────────────────────────────────────────────
Comparing with RIGHT tells us WHERE the drop is:
If nums[mid] > nums[right]:
↓
Drop is to the RIGHT of mid
Minimum is to the RIGHT
Search right: left = mid + 1
If nums[mid] < nums[right]:
↓
No drop to the right (sorted)
Minimum is on LEFT or IS mid
Search left: right = mid
Comparing with LEFT only tells us if left side is sorted,
but NOT where the minimum is located!
Example: [4, 5, 6, 7, 0, 1, 2]
↑ ↑ ↑
left mid right
nums[mid] = 7 > nums[right] = 2
There's a break to the right!
Minimum is in [0, 1, 2] ✓
The Two Cases Visualized
CASE 1: nums[mid] > nums[right]
═══════════════════════════════════════════════════════════════
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
mid right
nums[mid] = 7 > nums[right] = 2
What this means:
- There's a rotation point between mid and right
- Mid is in the larger sorted portion
- Minimum is somewhere to the RIGHT of mid
Action: left = mid + 1 (search right)
Visualization:
[4, 5, 6, 7, 0, 1, 2]
└─sorted─┘ ↓ └─sorted─┘
drop here!
The drop is to the right!
CASE 2: nums[mid] <= nums[right]
═══════════════════════════════════════════════════════════════
[6, 7, 0, 1, 2, 4, 5]
↑ ↑
mid right
nums[mid] = 0 < nums[right] = 5
What this means:
- No rotation point between mid and right
- Mid to right is sorted normally
- Minimum is at mid or to the LEFT of mid
Action: right = mid (search left, keep mid)
Visualization:
[6, 7, 0, 1, 2, 4, 5]
└─┘ ↓ └─────sorted───┘
drop
Mid to right is sorted, so minimum is left!
Why This Works
The rotation creates exactly ONE break point:
[larger values] → [smaller values]
Original: [0, 1, 2, 3, 4, 5, 6, 7]
Rotated: [4, 5, 6, 7, 0, 1, 2, 3]
└─sorted─┘ ↓ └─sorted─┘
break
At the break:
nums[i] > nums[i+1] (only place this happens!)
nums[i+1] is the minimum!
Binary search finds this break:
Compare mid with right
Move towards the break
Eventually: left == right at minimum!
🎯 Approach 1: Linear Search (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Scan array to find minimum:
Track smallest value seen
Return it
Implementation
public int findMin(int[] nums) {
int min = nums[0];
for (int num : nums) {
min = Math.min(min, num);
}
return min;
}
⏰ Time: O(n) - Check every element
💾 Space: O(1) - Only variables
❌ Problem: Doesn't meet O(log n) requirement! Doesn't use rotated sorted property!
🎯 Approach 2: Binary Search (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
The minimum is at the rotation point!
Use modified binary search:
Compare mid with right boundary
Move towards the rotation point
Key: Compare with RIGHT, not left!
The Strategy:
Modified Binary Search:
1. If nums[mid] > nums[right]:
Minimum is to the right
left = mid + 1
2. Else (nums[mid] <= nums[right]):
Minimum is at mid or left
right = mid
3. When left == right:
Found minimum!
Implementation
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// Compare mid with right boundary
if (nums[mid] > nums[right]) {
// Minimum is in right half
// Mid cannot be minimum (it's larger than right)
left = mid + 1;
} else {
// Minimum is in left half or IS mid
// Keep mid in search range
right = mid;
}
}
// When left == right, we found the minimum
return nums[left];
}
⏰ Time: O(log n) - Binary search
💾 Space: O(1) - Only pointers
🔍 Dry Run
Example 1: nums = [3, 4, 5, 1, 2]
Goal: Find minimum (should be 1)
Initial: left = 0, right = 4
[3, 4, 5, 1, 2]
↑ ↑
left right
Iteration 1:
mid = 0 + (4 - 0) / 2 = 2
nums[mid] = 5, nums[right] = 2
5 > 2, minimum is to the right
left = 3
[3, 4, 5, 1, 2]
↑ ↑
left right
Iteration 2:
mid = 3 + (4 - 3) / 2 = 3
nums[mid] = 1, nums[right] = 2
1 < 2, minimum is at mid or left
right = 3
[3, 4, 5, 1, 2]
↑
left/right
Loop ends (left == right)
return nums[3] = 1 ✓
Example 2: nums = [4, 5, 6, 7, 0, 1, 2]
Initial: left = 0, right = 6
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
left right
Iteration 1:
mid = 3
nums[3] = 7, nums[6] = 2
7 > 2, minimum to the right
left = 4
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
left right
Iteration 2:
mid = 5
nums[5] = 1, nums[6] = 2
1 < 2, minimum at mid or left
right = 5
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
left right
Iteration 3:
mid = 4
nums[4] = 0, nums[5] = 1
0 < 1, minimum at mid or left
right = 4
[4, 5, 6, 7, 0, 1, 2]
↑
left/right
Loop ends
return nums[4] = 0 ✓
Example 3: nums = [11, 13, 15, 17] (no rotation)
Initial: left = 0, right = 3
[11, 13, 15, 17]
↑ ↑
left right
Iteration 1:
mid = 1
nums[1] = 13, nums[3] = 17
13 < 17, minimum at mid or left
right = 1
[11, 13, 15, 17]
↑ ↑
left right
Iteration 2:
mid = 0
nums[0] = 11, nums[1] = 13
11 < 13, minimum at mid or left
right = 0
[11, 13, 15, 17]
↑
left/right
Loop ends
return nums[0] = 11 ✓
Example 4: nums = [2, 1] (rotated once)
Initial: left = 0, right = 1
[2, 1]
↑ ↑
left right
Iteration 1:
mid = 0
nums[0] = 2, nums[1] = 1
2 > 1, minimum to the right
left = 1
[2, 1]
↑
left/right
Loop ends
return nums[1] = 1 ✓
🎯 Why This Works - Deep Dive
The Rotation Point Property:
═══════════════════════════════════════════════════════════════
In a rotated sorted array:
Original: [0, 1, 2, 3, 4, 5, 6]
Rotated: [4, 5, 6, 0, 1, 2, 3]
There's exactly ONE point where:
nums[i] > nums[i+1]
This is the rotation point!
nums[i+1] is the MINIMUM!
Why Compare with Right?
═══════════════════════════════════════════════════════════════
We need to determine: Is minimum left or right of mid?
Case 1: nums[mid] > nums[right]
Example: [4, 5, 6, 7, 0, 1, 2]
↑ ↑
mid right
If mid value > right value:
There's a "break" between mid and right
Values decrease somewhere to the right
Minimum is to the right!
Why? In a sorted array, mid < right always
But here mid > right means rotation to the right
Case 2: nums[mid] <= nums[right]
Example: [6, 7, 0, 1, 2, 4, 5]
↑ ↑
mid right
If mid value <= right value:
No break between mid and right
Mid to right is sorted normally
Minimum is at mid or left!
Why? This portion is sorted, so minimum is not here
(unless mid itself is minimum)
Why NOT Compare with Left? (DETAILED EXPLANATION)
═══════════════════════════════════════════════════════════════
Let's prove why comparing with left doesn't work:
Test Case 1: [4, 5, 6, 7, 0, 1, 2]
↑ ↑
left mid
Compare nums[mid] with nums[left]:
nums[mid] = 7, nums[left] = 4
Result: 7 > 4
Interpretation:
Left side is sorted [4, 5, 6, 7] ✓
But where's the minimum?
- Could be at left (4)? NO, it's 0!
- Could be on right? YES, it's 0!
AMBIGUOUS ANSWER! ✗
Test Case 2: [0, 1, 2, 4, 5, 6, 7] (no rotation)
↑ ↑
left mid
Compare nums[mid] with nums[left]:
nums[mid] = 4, nums[left] = 0
Result: 4 > 0
Interpretation:
Left side is sorted [0, 1, 2, 4] ✓
But where's the minimum?
- At left (0)? YES! It's 0!
SAME comparison (mid > left) but DIFFERENT answer!
Case 1: Minimum on RIGHT
Case 2: Minimum on LEFT
COMPLETELY AMBIGUOUS! ✗
Test Case 3: [6, 7, 0, 1, 2, 4, 5]
↑ ↑
left mid
Compare nums[mid] with nums[left]:
nums[mid] = 0, nums[left] = 6
Result: 0 < 6
Interpretation:
There's a rotation in left portion
Minimum could be at mid OR further left?
Mid IS minimum (0) in this case!
But how do we know without checking? UNCLEAR! ✗
WHY LEFT COMPARISON FAILS:
────────────────────────────────────────────────────────────
Comparing with LEFT tells us:
"Is the LEFT portion sorted?"
But we need to know:
"Where is the MINIMUM?"
These are DIFFERENT questions!
A sorted left portion doesn't tell us where the minimum is!
WHY RIGHT COMPARISON WORKS:
────────────────────────────────────────────────────────────
Comparing with RIGHT tells us:
"Is there a DROP between mid and right?"
The DROP is exactly where the minimum is!
If nums[mid] > nums[right]:
DROP exists to the right → Minimum on right! ✓
If nums[mid] < nums[right]:
NO drop to the right → Minimum on left/mid! ✓
CLEAR, UNAMBIGUOUS, ALWAYS CORRECT!
The Mathematical Proof:
────────────────────────────────────────────────────────────
In a rotated sorted array, the minimum is where:
nums[i] > nums[i+1] (the break point)
When nums[mid] > nums[right]:
There MUST be a break between mid and right
(because in normal sorted array, mid < right always)
When nums[mid] < nums[right]:
There's NO break between mid and right
They're sorted normally
Break must be elsewhere (left) or mid IS minimum
If we compare nums[mid] with nums[left]:
We can't determine which side has minimum clearly
Example: [4, 5, 6, 7, 0, 1, 2]
↑ ↑
left mid
nums[mid] = 7 > nums[left] = 4
Is minimum left or right? Unclear!
Could be either side!
But comparing with right:
nums[mid] = 7 > nums[right] = 2
Clear: minimum is to the right!
The Loop Condition: left < right
═══════════════════════════════════════════════════════════════
Why left < right and not left <= right?
When we do right = mid:
We keep mid in search space
We DON'T do right = mid - 1
This means:
Eventually left and right converge to same index
That index is the minimum!
If we used left <= right:
When left == right, we'd do one more iteration
And potentially move past the answer
The Update Strategy:
═══════════════════════════════════════════════════════════════
When nums[mid] > nums[right]:
left = mid + 1
Why +1? Mid is definitely not minimum
(it's greater than right, so not smallest)
When nums[mid] <= nums[right]:
right = mid
Why not mid - 1? Mid COULD be minimum!
We need to keep it in search space
This asymmetry is intentional and crucial!
Alternative Approaches (Less Optimal)
// Approach: Compare with left (more complex logic)
if (nums[mid] > nums[left]) {
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
} else {
right = mid;
}
// Works but more complex!
// Approach: Find rotation point then return
// Two-pass approach, still O(log n) but less elegant
⚠️ Common Mistakes to Avoid
Mistake 1: Comparing with left instead of right
// ❌ WRONG - Logic becomes very complex
if (nums[mid] > nums[left]) {
// Can't determine clearly!
}
// ✓ CORRECT - Clear logic
if (nums[mid] > nums[right]) {
// Minimum is to the right
}
Mistake 2: Using left <= right
// ❌ WRONG - Doesn't work with right = mid
while (left <= right) {
// ...
right = mid; // Infinite loop risk!
}
// ✓ CORRECT
while (left < right) {
// Terminates when left == right
}
Mistake 3: Using right = mid - 1
// ❌ WRONG - Might skip the minimum
if (nums[mid] <= nums[right]) {
right = mid - 1; // Lost mid!
}
// ✓ CORRECT - Keep mid in range
if (nums[mid] <= nums[right]) {
right = mid; // Mid could be answer
}
Mistake 4: Returning wrong value
// ❌ WRONG - Returning mid instead of nums[left]
return mid; // This is an index!
// ✓ CORRECT
return nums[left]; // Return the value
Mistake 5: Not handling no rotation case
// ❌ WRONG - Special case for sorted
if (nums[0] < nums[n-1]) {
return nums[0]; // Unnecessary!
}
// ✓ CORRECT - Algorithm handles it naturally
// No special case needed!
🎯 Pattern Recognition
Problem Type: Binary Search - Find Rotation Point/Minimum
Core Pattern: Modified Binary Search with Right Comparison
When to Apply:
✓ Rotated sorted array
✓ All elements unique
✓ Need to find minimum
✓ Need O(log n) time
✓ Find rotation/pivot point
Recognition Keywords:
- "Rotated sorted array"
- "Find minimum"
- "All unique elements"
- O(log n) complexity
- Rotation point
Similar Problems:
- Search in Rotated Sorted Array (LC 33)
- Find Minimum in Rotated Sorted Array II (LC 154) - with duplicates
- Find Peak Element (LC 162)
Key Difference from Search in Rotated Array:
┌────────────────────────────────────────────┐
│ Search in Rotated (LC 33): │
│ - Find specific target value │
│ - Need to identify sorted half │
│ - More complex logic │
│ │
│ Find Minimum (This Problem): │
│ - Find minimum (rotation point) │
│ - Compare mid with right │
│ - Simpler, elegant logic │
└────────────────────────────────────────────┘
This is SIMPLER than search because we just
need to find the break point!
🧠 Interview Strategy
Step 1: "Minimum is at rotation point"
Step 2: "Compare mid with right boundary"
Step 3: "If mid > right, search right half"
Step 4: "Else search left half, keep mid"
Step 5: "When left == right, found minimum"
Key Points to Mention:
- Minimum is at rotation point (the "break")
- Compare mid with RIGHT (not left)
- Two cases based on comparison
- Use left < right (not <=)
- Use right = mid (not mid - 1)
- Asymmetric updates are intentional
- Time: O(log n), Space: O(1)
- Handles no-rotation case naturally
Why This Approach?
"In a rotated sorted array, there's exactly one break point
where larger values transition to smaller values. The minimum
is at this break point. I'll use modified binary search by
comparing mid with the right boundary. If nums[mid] > nums[right],
there's a rotation to the right, so I search the right half.
Otherwise, the minimum is at mid or to the left, so I keep mid
in the search range by setting right = mid. This converges to
the minimum in O(log n) time."
Why Compare with Right?
"Comparing with the right boundary gives clear information. If
mid is greater than right, we know there's a break point between
them, so minimum is to the right. If mid is less than or equal
to right, that portion is sorted, so minimum is to the left or
is mid itself."
Loop Condition:
"I use left < right because when I find a potential answer, I
set right = mid to keep it in the search space. This means left
and right will converge to the same index, which is the minimum."
🎓 How to Develop Intuition for Edge Cases (CRITICAL!)
This section teaches you how to catch bugs BEFORE they happen and develop intuition for tricky binary search problems.
🔴 The Common Bug (That You Might Write!)
// ❌ BUGGY CODE - Looks correct but fails edge cases!
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left <= right) { // ⚠️ Bug 1
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1; // ✓ Correct
} else {
right = mid - 1; // ❌ Bug 2: Should be right = mid
}
}
return nums[left];
}
Why does this fail? Let's trace a simple case:
Input: [3, 1, 2]
Initial: left = 0, right = 2
[3, 1, 2]
↑ ↑
Iteration 1:
mid = 1
nums[1] = 1, nums[2] = 2
1 < 2, so else branch
right = mid - 1 = 0 ← We just SKIPPED the answer (1)!
Now: left = 0, right = 0
Returns nums[0] = 3 ✗ WRONG!
Expected: 1
Got: 3
🎯 Method 1: Always Test Small Arrays First!
The Golden Rule: Before submitting ANY binary search solution, test these:
// Test Set 1: Size 1
[1] → Expected: 1
// Test Set 2: Size 2 (all cases)
[1, 2] → Expected: 1 (no rotation)
[2, 1] → Expected: 1 (rotated once)
// Test Set 3: Size 3 (critical!)
[1, 2, 3] → Expected: 1 (no rotation)
[3, 1, 2] → Expected: 1 (rotated at position 1) ← Catches the bug!
[2, 3, 1] → Expected: 1 (rotated at position 2)
// Test Set 4: Boundaries
[1, 2, 3, 4, 5] → Expected: 1 (min at start)
[5, 1, 2, 3, 4] → Expected: 1 (min at position 1)
[2, 3, 4, 5, 1] → Expected: 1 (min at end)
Pro Tip: Trace [3, 1, 2] by hand with your code. If it fails, you found your bug!
🔍 Method 2: The Loop Invariant Check
Ask yourself: "What must remain true after each iteration?"
Loop Invariant:
"If the minimum exists, it MUST be in range [left, right]"
Now check each branch:
Branch 1: if (nums[mid] > nums[right])
mid is in larger portion
mid CANNOT be minimum
✓ left = mid + 1 (exclude mid, invariant preserved)
Branch 2: else (nums[mid] <= nums[right])
mid COULD BE the minimum
If we do: right = mid - 1
We EXCLUDE mid
If mid is minimum, we LOSE it!
Invariant BROKEN! ✗
If we do: right = mid
We KEEP mid in range
Invariant PRESERVED! ✓
⚖️ Method 3: The Asymmetry Pattern Recognition
In "Find Minimum/Maximum/First/Last" problems, updates are ASYMMETRIC:
Rule: Can we definitively EXCLUDE mid?
If YES (mid is definitely NOT the answer):
✓ Use mid ± 1 to exclude it
If NO (mid MIGHT BE the answer):
✓ Use mid to KEEP it in range
❌ DON'T use mid ± 1
This problem:
if (nums[mid] > nums[right]) {
left = mid + 1; ✓ mid is NOT minimum (too large)
} else {
right = mid; ✓ mid MIGHT BE minimum, keep it!
}
Both can't use ±1 → ASYMMETRIC! This is correct!
🔄 Method 4: Loop Condition Consistency Check
Rule: If ANY update uses "= mid" (without ±1)
→ Loop MUST be "left < right" (not <=)
Why?
With left <= right and right = mid:
When left == right, mid == left
right = mid means right = left
Loop continues: left <= right still true
→ INFINITE LOOP!
With left < right and right = mid:
When left == right - 1, mid == left
right = mid = left
→ left == right → loop exits ✓
Checklist:
❌ left <= right with right = mid → DANGER!
✓ left < right with right = mid → SAFE!
✓ left <= right with right = mid - 1 → SAFE!
📋 The Paper Trace Technique
Most Powerful Debugging Method:
- Pick a 3-element array:
[3, 1, 2](minimum in middle) - Trace your code step by step ON PAPER:
[3, 1, 2] target = find minimum (1)
Step 1: left = 0, right = 2, mid = 1
nums[1] = 1, nums[2] = 2
1 < 2 → else branch
Your code: right = mid - 1 = 0
Range now: [3] (just index 0)
But answer 1 is at index 1!
BUG FOUND! ✗
Step 2 (if you had continued):
left = 0, right = 0
Returns nums[0] = 3
WRONG! ✗
If you can't trace it on paper, you don't understand it!
🎯 The Systematic Testing Strategy
For EVERY binary search problem:
Phase 1: Unit Tests (30 seconds)
✓ [1]
✓ [1, 2]
✓ [2, 1]
✓ [3, 1, 2] ← This catches 90% of bugs!
Phase 2: Boundary Tests (30 seconds)
✓ Answer at start
✓ Answer at end
✓ Answer in middle
Phase 3: Special Cases (if applicable)
✓ No rotation
✓ Full rotation
✓ Duplicates (if allowed)
Total: 2 minutes to save hours of debugging!
🔑 The Universal Binary Search Checklist
Before submitting any binary search code, verify:
✓ Loop condition matches update style:
- If using "= mid" anywhere → use "left < right"
- If using "± 1" everywhere → use "left <= right"
✓ Asymmetry is intentional:
- If one branch uses "mid + 1" and other uses "mid"
- This is CORRECT for find first/last/min/max problems!
✓ Tested on [3, 1, 2]:
- Trace by hand
- Verify it returns 1
✓ Loop invariant holds:
- After each iteration, answer is still in [left, right]
✓ No off-by-one errors:
- Check what happens when left == right - 1
💡 The Key Learning
Binary search on "find minimum/maximum/first/last":
- Updates are ASYMMETRIC (one uses mid, other uses mid±1)
- Loop condition is "left < right" (not <=)
- ONE branch keeps mid in range
Binary search on "exact match":
- Updates are SYMMETRIC (both use mid±1)
- Loop condition is "left <= right"
- Return when found, not after loop
Different patterns → Different rules!
🎓 Practice Exercise
Fix this buggy code by hand (don't run it):
// Buggy
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid - 1; // Bug here
}
}
// Test on: [3, 1, 2]
// Trace it step by step
// Where does it fail?
// Fix:
// 1. Change loop condition to: left < right
// 2. Change right = mid - 1 to: right = mid
If you can trace and fix this mentally, you've mastered the pattern! ✓
📝 Quick Revision Notes
🎯 Core Concept:
Find Minimum in Rotated Array: Minimum is at rotation point (the break). Use binary search: compare mid with RIGHT. If nums[mid] > nums[right]: search right (left = mid + 1). Else: search left (right = mid). Loop: left < right. Return nums[left]!
⚡ Quick Implementation:
class Test {
public int findMin(int[] a) {
int left = 0;
int right = a.length - 1;
// since I do right = mid instead of right = mid -1, should
// be left < right instead of left <= right. Else infinite loop.
while (left < right) {
int mid = left + (right - left) / 2;
// Check where the drop (from big to small number) happened.
if(a[mid] > a[right]) {
// if drop is in 2nd half, we need to search in 2nd half.
// if a[mid] is the result, it will not be a[mid] > a[right]
left = mid + 1;
} else {
right = mid; // there is chance mid can be answer. So, cannot do mid - 1
}
}
return a[left];
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.findMin(new int[] {3,4,5,1,2}) == 1);
System.out.println(t.findMin(new int[] {4,5,6,7,0,1,2}) == 0);
System.out.println(t.findMin(new int[] {11,13,15,17}) == 11);
System.out.println(t.findMin(new int[] {1, 2, 3, 4, 5}) == 1);
System.out.println(t.findMin(new int[] {5, 1, 2, 3, 4}) == 1);
System.out.println(t.findMin(new int[] {2, 3, 4, 5, 1}) == 1);
System.out.println(t.findMin(new int[] {2, 1}) == 1);
System.out.println(t.findMin(new int[] {1, 2}) == 1);
System.out.println(t.findMin(new int[] {1}) == 1);
System.out.println(t.findMin(new int[] {4,5,6,7,8,9,10,11,12,0,1,2,3}) == 0);
}
}
🔑 Key Insights:
- Pattern: Find Rotation Point = Find Minimum
- Key Comparison:
nums[mid]vsnums[right](NOT left!) - Case 1:
mid > right→ break to right →left = mid + 1 - Case 2:
mid <= right→ sorted to right →right = mid - Loop:
left < right(NOT <=) - Asymmetric:
left = mid + 1butright = mid(intentional!) - Return:
nums[left]when loop ends - Time: O(log n), Space: O(1)
🎪 Memory Aid:
"Compare with RIGHT to find the break! Mid > Right? Go right! Else keep mid!"
Think: "Mid vs Right → Break detection → Minimum found!"
💡 The Key Insight:
Rotation creates ONE break point:
[larger values] → [smaller values]
↓
minimum here!
Compare mid with right:
mid > right: break is to the right
mid <= right: no break, sorted normally
⚠️ Critical Details:
1. Compare: nums[mid] vs nums[right] ← RIGHT!
2. Case 1: mid > right → left = mid + 1
3. Case 2: mid <= right → right = mid ← NOT mid-1
4. Loop: while (left < right) ← NOT <=
5. Return: nums[left] (or nums[right], same!)
6. No special case needed for sorted array
🚨 EDGE CASE ALERT - Test These!
Always test before submitting:
✓ [3, 1, 2] → Should return 1
✓ [2, 1] → Should return 1
✓ [1, 2, 3] → Should return 1
If these fail → Your right = mid - 1 is wrong!
Common Bug:
❌ right = mid - 1 (skips answer!)
✓ right = mid (keeps answer!)
Why Asymmetric Updates?
mid > right: mid is NOT answer → mid + 1
mid <= right: mid MIGHT BE answer → mid
This is CORRECT for find min/max problems!
🔥 Why Compare with Right:
Example: [4, 5, 6, 7, 0, 1, 2]
↑ ↑ ↑
left mid right
nums[mid] = 7, nums[right] = 2
7 > 2 → There's a break to the right!
→ Minimum is in [0, 1, 2]
If compared with left:
nums[mid] = 7, nums[left] = 4
7 > 4 → Both sides could have minimum!
→ Unclear which way to go
RIGHT comparison is CLEAR! ✓
💡 The Asymmetry:
Why left = mid + 1 but right = mid?
When mid > right:
mid is in the larger portion
mid CANNOT be minimum
So: left = mid + 1 (skip mid)
When mid <= right:
mid COULD be minimum
Must keep in search space
So: right = mid (keep mid)
This asymmetry finds the exact point!
🧪 Edge Cases
Case 1: No rotation (already sorted)
Input: nums = [1, 2, 3, 4, 5]
Output: 1
(Algorithm handles naturally, no special case!)
Case 2: Rotated once
Input: nums = [5, 1, 2, 3, 4]
Output: 1
Case 3: Rotated to last position
Input: nums = [2, 3, 4, 5, 1]
Output: 1
Case 4: Two elements - rotated
Input: nums = [2, 1]
Output: 1
Case 5: Two elements - not rotated
Input: nums = [1, 2]
Output: 1
Case 6: Single element
Input: nums = [1]
Output: 1
Case 7: Large rotation
Input: nums = [4,5,6,7,8,9,10,11,12,0,1,2,3]
Output: 0
All handled correctly! ✓
Related Patterns
- Search in Rotated Sorted Array (LC 33) - Similar concept, find target
- Find Minimum in Rotated Sorted Array II (LC 154) - With duplicates (harder)
- Find Peak Element (LC 162) - Similar binary search modification
Happy practicing! 🎯
Note: This is one of the most elegant binary search problems! The key is comparing with RIGHT boundary - it makes the logic crystal clear. Master this pattern!