LeetCode 278: First Bad Version (Binary Search Boundary)

2026-03-19 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 278Binary SearchBoundaryInterview

Today we solve LeetCode 278 - First Bad Version.

Source: https://leetcode.com/problems/first-bad-version/

English

Problem Summary

You are given versions 1..n, and an API isBadVersion(version). Once a version is bad, all later versions are bad too. Return the first bad version.

Key Insight

The predicate is monotonic: false, false, ..., false, true, true, .... We need the leftmost index where it becomes true, which is exactly a binary-search boundary problem.

Brute Force and Limitations

Linear scan from version 1 to n is O(n) API calls, too slow when n is large.

Optimal Algorithm Steps

1) Set left = 1, right = n.
2) While left < right, compute mid = left + (right - left) / 2.
3) If isBadVersion(mid) is true, keep left half including mid: right = mid.
4) Otherwise discard left half: left = mid + 1.
5) Loop ends at the first bad version: left.

Complexity Analysis

Time: O(log n) API calls.
Space: O(1).

Common Pitfalls

- Using while (left <= right) with wrong updates and missing the boundary.
- Integer overflow in midpoint if using (left + right)/2 directly in some languages.
- Returning mid immediately when it's bad (not guaranteed to be first).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

func firstBadVersion(n int) int {
    left, right := 1, n
    for left < right {
        mid := left + (right-left)/2
        if isBadVersion(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  return function(n) {
    let left = 1, right = n;
    while (left < right) {
      const mid = left + Math.floor((right - left) / 2);
      if (isBadVersion(mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };
};

中文

题目概述

给你版本号区间 1..n，并提供 API isBadVersion(version)。一旦某个版本是坏的，后续版本都坏。请返回第一个坏版本。

核心思路

这是典型的单调布尔序列：前面全是 false，后面全是 true。目标是找到第一个 true 的位置，也就是二分查找左边界。

暴力解法与不足

从 1 到 n 逐个调用 API 的线性扫描是 O(n)，在大规模输入下不够高效。

最优算法步骤

1）初始化 left = 1，right = n。
2）当 left < right 时，计算 mid = left + (right - left) / 2。
3）若 isBadVersion(mid) 为真，说明首个坏版本在左半区（含 mid），令 right = mid。
4）否则首个坏版本在右半区，令 left = mid + 1。
5）循环结束时 left 就是答案。

复杂度分析

时间复杂度：O(log n)（API 调用次数）。
空间复杂度：O(1)。

常见陷阱

- 边界更新不严谨导致死循环或错过答案。
- 中点写成 (left + right)/2 可能在部分语言里溢出。
- mid 一旦为 bad 就立刻返回，可能不是第一个 bad。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

func firstBadVersion(n int) int {
    left, right := 1, n
    for left < right {
        mid := left + (right-left)/2
        if isBadVersion(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  return function(n) {
    let left = 1, right = n;
    while (left < right) {
      const mid = left + Math.floor((right - left) / 2);
      if (isBadVersion(mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };
};