57. First Bad Version
🔗 LeetCode Problem: 278. First Bad Version
📊 Difficulty: Easy
🏷️ Topics: Binary Search, Interactive
Problem Statement
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Example 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
Example 2:
Input: n = 1, bad = 1
Output: 1
Constraints:
- 1 <= bad <= n <= 2^31 - 1
🎨 Visual Understanding
The Problem Visualized
Versions: [1, 2, 3, 4, 5, 6, 7, 8]
Status: [G, G, G, G, B, B, B, B]
↑ ↑
Good First Bad!
G = Good version
B = Bad version
Once a bad version appears, ALL following versions are bad.
Find the FIRST bad version.
Example: n = 8, first bad = 5
Versions: 1 2 3 4 5 6 7 8
Status: G G G G B B B B
↑
Answer: 5
Pattern: GGGG BBBB
We need to find the transition point from G to B!
🚨 CRITICAL INSIGHT - Why Binary Search Works
The Key Pattern!
Versions follow a pattern:
[GOOD GOOD GOOD ... GOOD | BAD BAD BAD ... BAD]
↑
Transition point!
This is a SORTED sequence:
- All versions < first bad are GOOD
- All versions >= first bad are BAD
Since it's sorted (monotonic), we can use BINARY SEARCH!
The Search Space:
Not searching an array
Searching a RANGE: [1, 2, 3, ..., n]
Each "element" is a version number
Each version has a property: good or bad
The Goal:
Find FIRST position where property changes from good to bad
= Find LEFTMOST bad version
= "Find First Occurrence" pattern!
Why This is Binary Search on Answer Space
Traditional Binary Search:
Search in array for value
This Problem:
Search in RANGE [1..n] for version
But the pattern is the same:
Can eliminate half the search space at each step!
How?
Check version at mid:
If bad: first bad is at mid or left of mid
If good: first bad is right of mid
Either way, eliminate half!
Example: versions 1-8, first bad = 5
Check mid = 4:
isBadVersion(4) = false (good)
So first bad must be > 4
Eliminate left half: [1,2,3,4]
Search right half: [5,6,7,8]
Check mid = 6:
isBadVersion(6) = true (bad)
So first bad is at 6 or left of 6
Eliminate right half: [7,8]
Search left half: [5,6]
Check mid = 5:
isBadVersion(5) = true (bad)
So first bad is at 5 or left of 5
But no elements left of 5 in our range
Answer: 5 ✓
The Binary Search Invariant
Throughout the search:
All versions < left: definitely good
All versions > right: definitely bad (or unknown)
When we find a bad version:
It MIGHT be the first, or first might be to its left
Keep searching left!
When we find a good version:
First bad is definitely to its right
Move right!
When loop ends:
left = first bad version ✓
🎯 Approach 1: Linear Search (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Start from version 1 and check each version:
If version i is bad, it's the first bad version
(because all previous were good)
Implementation
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
// Check each version from 1 to n
for (int i = 1; i <= n; i++) {
if (isBadVersion(i)) {
return i; // First bad version found
}
}
return n; // If all checked, last one must be bad
}
}
⏰ Time: O(n) - Check each version
💾 Space: O(1) - Only variables
Why This Works:
We check versions in order: 1, 2, 3, ...
First time we see bad, all previous were good
So that's the first bad version!
❌ Problem: Too slow! If n = 2 billion, too many API calls!
🎯 Approach 2: Binary Search (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Versions form a pattern: GGGG...GBBBB...B
This is MONOTONIC!
We're looking for the TRANSITION point
= FIRST position where it becomes bad
= "Find First Occurrence" of bad version
Binary Search on Range [1, n]:
If mid is bad: first bad is at mid or left
If mid is good: first bad is to the right
This is the "Find First/Lower Bound" pattern!
The Strategy:
Standard binary search with modification:
When we find a bad version:
Don't return immediately!
Track it as potential answer
Continue searching LEFT (maybe earlier bad version)
When we find a good version:
First bad must be to the RIGHT
After loop: we've found the leftmost bad version!
Implementation
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right) { // Note: < not <=
// Safe mid calculation (prevent overflow)
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
// mid is bad, but might not be first
// First bad could be at mid or left of mid
// Search left half (including mid)
right = mid; // Note: mid, not mid - 1
} else {
// mid is good
// First bad must be right of mid
// Search right half (excluding mid)
left = mid + 1;
}
}
// When left == right, we've found first bad version
return left;
}
}
⏰ Time: O(log n) - Binary search
💾 Space: O(1) - Only pointers
🔍 Dry Run
Example: n = 8, first bad = 5
Versions: [1, 2, 3, 4, 5, 6, 7, 8]
Status: [G, G, G, G, B, B, B, B]
↑
First Bad
Initial: left = 1, right = 8
[1, 2, 3, 4, 5, 6, 7, 8]
↑ ↑
left right
Iteration 1:
mid = 1 + (8 - 1) / 2 = 4
isBadVersion(4) = false (good)
First bad is right of 4
left = 5
[1, 2, 3, 4, 5, 6, 7, 8]
↑ ↑
left right
Iteration 2:
mid = 5 + (8 - 5) / 2 = 6
isBadVersion(6) = true (bad)
First bad could be at 6 or left
right = 6
[1, 2, 3, 4, 5, 6, 7, 8]
↑ ↑
left right
Iteration 3:
mid = 5 + (6 - 5) / 2 = 5
isBadVersion(5) = true (bad)
First bad could be at 5 or left
right = 5
[1, 2, 3, 4, 5, 6, 7, 8]
↑
left/right
Loop ends (left == right)
return left = 5 ✓
API calls: 3 (much better than 8!)
Example: n = 5, first bad = 4
Versions: [1, 2, 3, 4, 5]
Status: [G, G, G, B, B]
↑
First Bad
Initial: left = 1, right = 5
[1, 2, 3, 4, 5]
↑ ↑
left right
Iteration 1:
mid = 1 + (5 - 1) / 2 = 3
isBadVersion(3) = false (good)
left = 4
[1, 2, 3, 4, 5]
↑ ↑
left right
Iteration 2:
mid = 4 + (5 - 4) / 2 = 4
isBadVersion(4) = true (bad)
right = 4
[1, 2, 3, 4, 5]
↑
left/right
Loop ends (left == right)
return left = 4 ✓
API calls: 2
Example: n = 1, first bad = 1
Versions: [1]
Status: [B]
↑
First Bad
Initial: left = 1, right = 1
[1]
↑
left/right
Loop condition: left < right
1 < 1 = false
Loop doesn't run!
return left = 1 ✓
API calls: 0 (no need to check!)
🎯 Why This Works - Deep Dive
The Loop Condition: while (left < right)
═══════════════════════════════════════════════════════════════
Why not left <= right?
We want left and right to converge to same position
When left == right, we've found the answer
No need to continue!
The Pointer Updates:
═══════════════════════════════════════════════════════════════
When isBadVersion(mid) = true:
right = mid (NOT mid - 1)
Why?
mid itself is bad, could be first bad
Don't eliminate mid!
When isBadVersion(mid) = false:
left = mid + 1 (NOT mid)
Why?
mid is good, can't be first bad
First bad must be after mid
Eliminate mid!
Loop Invariant:
═══════════════════════════════════════════════════════════════
Throughout the search:
All versions < left: definitely good
All versions >= left, <= right: unknown
First bad version is in range [left, right]
As loop progresses:
Range [left, right] keeps shrinking
Always contains first bad version
When left == right:
Range is single element
That's the first bad version!
Why This Pattern is Different:
═══════════════════════════════════════════════════════════════
Classic Binary Search:
while (left <= right)
left = mid + 1
right = mid - 1
Return mid when found, -1 if not
Find First Occurrence:
while (left < right)
left = mid + 1 (when can eliminate)
right = mid (when might be answer)
Return left after loop
The "right = mid" is the KEY difference!
Keeps potential answer in range!
The "Find First" Pattern
This is a template for "Find First Occurrence":
1. Loop: while (left < right)
2. When property is TRUE:
right = mid (keep mid in range)
3. When property is FALSE:
left = mid + 1 (eliminate mid)
4. Return: left after loop
Applies to:
- Find first bad version
- Find first element >= target
- Find first element satisfying condition
- Find leftmost position
Key insight:
right = mid preserves the answer
left = mid + 1 eliminates impossibilities
⚠️ Common Mistakes to Avoid
Mistake 1: Using left <= right with wrong updates
// ❌ WRONG - Can create infinite loop
while (left <= right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid; // With <=, creates infinite loop!
} else {
left = mid + 1;
}
}
// ✓ CORRECT - Use left < right
while (left < right) {
// ...
}
Why it's wrong:
With left <= right and right = mid:
[4, 5], left = 4, right = 5
mid = 4, bad = true
right = mid = 4
Now: left = 4, right = 4
Loop continues (4 <= 4)
mid = 4 again
Infinite loop!
With left < right:
Loop ends when left == right ✓
Mistake 2: Using right = mid - 1 when bad
// ❌ WRONG - Might skip the answer
if (isBadVersion(mid)) {
right = mid - 1; // What if mid is first bad?
}
// ✓ CORRECT - Keep mid in range
if (isBadVersion(mid)) {
right = mid; // mid could be the answer
}
Why it's wrong:
If mid is the first bad version:
right = mid - 1 eliminates it!
We'll never find it!
Example: versions 1-5, first bad = 3
left = 1, right = 5
mid = 3, bad = true
right = mid - 1 = 2
Now searching [1,2]
Will never find 3!
Mistake 3: Using (left + right) / 2
// ❌ WRONG - Overflow risk
int mid = (left + right) / 2;
// ✓ CORRECT - Safe from overflow
int mid = left + (right - left) / 2;
Why it matters:
n can be up to 2^31 - 1
If left = 1,000,000,000 and right = 2,000,000,000
left + right = 3,000,000,000 > Integer.MAX_VALUE
Integer overflow!
left + (right - left) / 2 is always safe
🎯 Pattern Recognition
Problem Type: Binary Search - Find First Occurrence
Core Pattern: Find Leftmost Position with Property
When to Apply:
✓ Searching in a RANGE (not array)
✓ Looking for FIRST element with property
✓ Property follows MONOTONIC pattern: FFFF...FTTT...T
✓ Need to minimize checks/API calls
✓ O(log n) time required
Recognition Keywords:
- "First" + some property
- "Minimize calls to API"
- "Range of versions/numbers"
- Pattern: good...good bad...bad
- Binary search on answer space
Similar Problems:
- Search Insert Position (LC 35)
- Find Smallest Letter Greater Than Target (LC 744)
- Find First and Last Position (LC 34)
- H-Index II (LC 275)
- Sqrt(x) (LC 69)
Key Difference from Standard Binary Search:
┌────────────────────────────────────────────┐
│ Standard Binary Search: │
│ - while (left <= right) │
│ - right = mid - 1 always │
│ - Return mid when found │
│ │
│ Find First Pattern (This Problem): │
│ - while (left < right) │
│ - right = mid when might be answer │
│ - Return left after loop │
└────────────────────────────────────────────┘
The "right = mid" preserves potential answer!
🧠 Interview Strategy
Step 1: "Pattern is monotonic: good...good bad...bad"
Step 2: "This is binary search on range [1, n]"
Step 3: "Find FIRST bad = Find leftmost occurrence pattern"
Step 4: "Use loop condition: left < right"
Step 5: "When bad: right = mid (keep answer)"
Step 6: "When good: left = mid + 1 (eliminate)"
Key Points to Mention:
- Recognize monotonic pattern: GGGG BBBB
- Binary search on RANGE, not array
- Looking for FIRST bad = leftmost bad
- Use "find first" template: left < right
- When bad, keep mid: right = mid
- When good, eliminate: left = mid + 1
- Return left after convergence
- Safe mid calculation prevents overflow
- Minimizes API calls: O(log n)
- Time: O(log n), Space: O(1)
Why This Approach?
"The versions follow a monotonic pattern - all good versions come
before all bad versions. This makes it perfect for binary search.
I'm looking for the FIRST bad version, which is the 'find first
occurrence' pattern. The key difference from standard binary search
is that when I find a bad version, I keep it in the search range
with right = mid, because it might be the first bad version. When
I find a good version, I eliminate it with left = mid + 1. The loop
condition left < right ensures convergence, and left will point to
the first bad version when the loop ends."
📝 Quick Revision Notes
🎯 Core Concept:
Find First Bad Version: Pattern is GGGG BBBB (monotonic). Use binary search on range [1, n] with "find first" template. When bad: right = mid (keep answer). When good: left = mid + 1 (eliminate). Loop condition: left < right.
⚡ Quick Implementation:
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) { // Note: < not <=
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid; // Keep mid (might be first)
} else {
left = mid + 1; // Eliminate mid
}
}
return left; // First bad version
}
}
🔑 Key Insights:
- Pattern: Find First Occurrence / Find Leftmost
- Monotonic: GGGG...G BBBB...B (sorted property)
- Loop:
left < right(not <=) - When Bad:
right = mid(preserve potential answer) - When Good:
left = mid + 1(eliminate impossibility) - Return:
left(convergence point) - Mid:
left + (right - left) / 2(safe from overflow) - Search Space: Range [1, n] not array
- API Calls: O(log n) - minimized
- Time: O(log n), Space: O(1)
🎪 Memory Aid:
"Good versions LEFT, bad versions RIGHT. Find the transition!"
Think: "GGGG | BBBB → Find the |!"
💡 The Key Insight:
When isBadVersion(mid) = true:
right = mid (NOT mid - 1)
Why? mid COULD be first bad!
When isBadVersion(mid) = false:
left = mid + 1 (NOT mid)
Why? mid CAN'T be first bad!
Loop: left < right (NOT <=)
Why? Stop when left == right (found it!)
⚠️ Critical Details:
1. Loop: while (left < right) ← Not <=
2. Bad: right = mid ← Not mid - 1
3. Good: left = mid + 1 ← Yes, + 1
4. Return: left ← Not right or left + 1
5. Mid: left + (right - left) / 2 ← Safe
6. Initialize: left = 1, right = n
🔥 Template for "Find First":
// Universal template for "find first occurrence"
class Test {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left <= right) {
int mid = right + (left - right) / 2;
if(isBadVersion(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// When left == right, we've found first bad version
return left;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.firstBadVersion(4));
}
}
Related Patterns
- Search Insert Position (LC 35) - Similar leftmost pattern
- Find Smallest Letter Greater Than Target (LC 744) - Same template
- Find First and Last Position (LC 34) - Uses this + find last
- Sqrt(x) (LC 69) - Binary search on answer space
Happy practicing! 🎯
Note: This is the CLASSIC "find first occurrence" template! Master it - you'll use it again and again in binary search problems!