278. First Bad Version

Imagine you're the product manager in charge of launching a new product. Everything is going great until — boom! — one of the versions fails the quality check.

The problem? Once a version turns out to be bad, every version that comes after it is also bad because each version builds on the one before it.

Now, suppose there are n versions, numbered from 1 to n. Your goal is simple: figure out which version was the first one that went bad.

Luckily, you have access to a helper function called isBadVersion(version). It tells you whether a particular version is bad.

Your task is to use this function smartly to find the first bad version — and do it using as few API calls as possible.

Example 1:

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

Explanation:
isBadVersion(3) → false
isBadVersion(5) → true
isBadVersion(4) → true
So version 4 is the first one that went wrong.

Example 2:

Input: n = 1, bad = 1
Output: 1

278. First Bad Version

Approach #1: Linear Scan (Brute Force)

The simplest way to solve this problem is by checking each version one by one until we find the first one that’s bad. This is called a linear scan or brute-force approach.

Here’s how that would look in Java:

// The isBadVersion API is defined in the parent class VersionControl
// boolean isBadVersion(int version);

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        for (int i = 1; i <= n; i++) {
            if (isBadVersion(i)) {
                return i;
            }
        }
        return n;
    }
}
  

Complexity Analysis

• Time Complexity: O(n) – In the worst case, we may check all versions from 1 to n.
• Space Complexity: O(1) – No extra space is used apart from a few variables.

This method is easy to understand but not efficient for large values of n. That’s why it often runs into Time Limit Exceeded errors on platforms like LeetCode.

Approach #2: Binary Search (Efficient & Accepted)

A much faster way to solve the problem is by using binary search. Instead of checking every version, we can eliminate half of the versions in each step.

Let’s understand this with two possible scenarios:

Scenario 1: isBadVersion(mid) returns false

  Versions:   1  2  3  4  5  6  7  8  9
              G  G  G  G  G  G  B  B  B
              |           |           |
            left         mid        right
  

If the middle version is good, we can ignore it and everything before it. So we shift left = mid + 1.

Scenario 2: isBadVersion(mid) returns true

  Versions:   1  2  3  4  5  6  7  8  9
              G  G  G  B  B  B  B  B  B
              |           |           |
            left         mid        right
  

If the middle version is bad, it might be the first bad one — or maybe an earlier version is the culprit. So we shift right = mid.

This way, we slowly narrow down the search space until left == right, which is our answer.

Binary Search Java Implementation

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
  

Complexity Analysis

• Time Complexity: O(log n) – We cut the search space in half each time.
• Space Complexity: O(1) – Just two pointers, no extra storage.

Important Notes

• Use int mid = left + (right - left) / 2 instead of (left + right)/2 to prevent integer overflow.
• This approach is fast and efficient — and usually the one accepted in coding interviews and competitive platforms.
• Binary search works best when the data has a sorted or predictable structure, like this one where all versions after the first bad version are also bad.

Fun fact: Even expert programmers have made the mistake of integer overflow in binary search — it went unnoticed in a famous book's implementation for over 20 years!

To find the first bad version quickly, the best approach is to use binary search. Instead of checking every version one by one, we check the middle version and narrow down the range based on the result.

Java Code: First Bad Version

Here’s how you can implement it in Java:

public int firstBadVersion(int n) {
    int left = 1;
    int right = n;

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

        if (isBadVersion(mid)) {
            right = mid; // Look in the left half
        } else {
            left = mid + 1; // Look in the right half
        }
    }

    return left; // First bad version
}
  

This code is using a binary search strategy. It starts with the entire range of versions and keeps splitting it in half.

- If the middle version is bad, we know the first bad version must be at that point or earlier, so we move the right pointer.
- If it’s good, then the first bad one must be after that, so we move the left pointer.

Eventually, both pointers will meet at the exact version where things started going wrong.

Why is the Time Complexity O(log n)?

The reason this algorithm is so efficient is because it cuts the search range in half every time. That’s the power of binary search.

In the worst case, you'll end up making around log₂(n) API calls — way fewer than checking all n versions one by one. That gives us a time complexity of O(log n).

This is much better than a brute-force solution with O(n) time complexity, especially when n is very large. Plus, since we’re only using two variables (left and right), the space complexity is just O(1).

Here’s the Java Code

/* 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 start = 1;
        int end = n;
        int result = 1;
        while(start <= end){
            int mid = start + (end-start)/2;
            if(isBadVersion(mid)){
                end = mid - 1;
                result = mid;
            }else
                start = mid + 1;
            }
        return result;
    }
}