Code Logo

First Bad Version

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for First Bad Version

Solution Approach

Binary search between 1 and n. If isBadVersion(mid) is true, search left; else search right.

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

Time O(log n), Space 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;
    }
}