← Back to Index

📚 First Bad Version – Java Cheat Sheet

📌 What Is It?

The First Bad Version problem involves finding the first bad version in a sequence of versions, where each version is either good or bad. Once a bad version is found, all subsequent versions are also bad. The goal is to find the first bad version using O(log N) time.

🧱 Pattern Template

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                right = mid; // Narrow down to the left half
            } else {
                left = mid + 1; // Narrow down to the right half
            }
        }

        return left; // The first bad version
    }
}

📊 Time Complexity

• Binary Search: O(log N) – Halving the search space at each step.

✅ Use Cases

• Finding the first occurrence of a condition in a sequence
• Applications in debugging and version control systems

📘 Common LeetCode Problems

• 278. First Bad Version [Easy] Binary Search

🧪 Example: First Bad Version

Input: n = 5, bad = 4
Output: 4

Explanation:
- Versions 1, 2, and 3 are good.
- Version 4 is the first bad version.

▶️ View Animation

💡 Pro Tips

• Always calculate the mid-point as mid = left + (right - left) / 2 to avoid overflow.
• Edge cases: single bad version, all versions bad, or no bad versions (if applicable).