Code Logo

First Bad Version

Published at24 Jul 2026
Created by
Easy 1 views
Like0

You are a product manager leading a team to develop a new product. Unfortunately, the latest version of your product has failed quality checks. Since each version is built on top of the previous one, all versions after a bad version are also bad. Given n versions and an API isBadVersion(version) that returns whether a version is bad, find the first bad version with the minimum number of API calls.

This is a classic binary search problem where the search space is the range of versions [1, n]. Call the API on the middle version. If it returns true (bad), the first bad version is in the left half, including mid. If it returns false (good), the first bad version is in the right half, after mid.

Each API call eliminates half of the remaining versions, requiring only O(log n) calls. A linear scan could require up to n calls, which would be infeasible for large n (up to 2³¹ - 1). The binary search approach makes at most 31 API calls for the maximum input.

Edge cases include n = 1 (only version 1, which is bad), the first version being bad (return 1), and the last version being the first bad one.

The key insight is the monotonic property of versions: once a version is bad, all later versions are also bad. This creates a clear threshold where good versions transition to bad. Binary search finds this threshold with minimal API calls.

Example Input & Output

Example 1
Input
5, isBadVersion=4
Output
4
Explanation

Version 4 is the first bad one.

Example 2
Input
10, isBadVersion=1
Output
1
Explanation

First version is bad.

Example 3
Input
1, isBadVersion=1
Output
1
Explanation

Only version, which is bad.

Example 4
Input
10, isBadVersion=10
Output
10
Explanation

Last version is the first bad.

Example 5
Input
3, isBadVersion=2
Output
2
Explanation

Version 2 is the first bad.

Algorithm Flow

Recommendation Algorithm Flow for First Bad Version

Solution Approach

Find the first bad version in a sequence of versions using an API that tells you whether a version is bad. Once a version becomes bad, all subsequent versions are also bad. Use binary search to find the boundary between good and bad versions. When isBadVersion(mid) returns true, the first bad version is at or before mid, so move right = mid. When it returns false, the first bad version is after mid, so move left = mid + 1.

function firstBadVersion(n) {
  var left = 1, right = n;
  while (left < right) {
    var mid = Math.floor((left + right) / 2);
    if (isBadVersion(mid)) right = mid;
    else left = mid + 1;
  }
  return left;
}

The API call isBadVersion(mid) provides the boolean check that guides the binary search. Once the search converges (left == right), that index is the first bad version. The condition left < right prevents infinite loops and ensures termination.

Time complexity is O(log n) with one API call per iteration, space complexity is O(1).

Best Answers

java
class Solution {
    static int bad = 4;
    static boolean isBadVersion(int v) { return v >= bad; }
    public int solution(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}