278. First Bad Version

On LeetCode ->

Reformulated question¶

Find the smallest version in 1..n such that isBadVersion(v) is True, knowing:

all versions before it are good
it and all later versions are bad
you should use as few API calls as possible

Compact example:

n=5, state=[good, good, good, bad, bad] -> 4

Key trick¶

Use binary search on the boundary between:

good prefix
bad suffix

Keep the first bad candidate and move left when mid is bad.

Trap¶

Common mistakes:

using linear search, which wastes API calls
off-by-one errors with left, right, and loop condition
forgetting to return the left boundary directly
initializing an answer variable unnecessarily
not handling n=1

Why this question is interesting¶

It is a clean "find first true" binary search.

It tests whether you really understand boundary-search, not just ordinary value lookup.

Solve the problem with idiomatic python¶

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n

        # Invariant:
        # - first bad version is always inside [left, right]
        while left < right:
            mid = left + (right - left) // 2

            if isBadVersion(mid):
                # mid can still be the first bad version
                right = mid
            else:
                # first bad version must be after mid
                left = mid + 1

        return left

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("n", "bad", "expected"),
    [
        (1, 1, 1),
        (2, 1, 1),
        (2, 2, 2),
        (5, 4, 4),
        (5, 1, 1),
        (5, 5, 5),
        (8, 3, 3),
        (10, 7, 7),
    ],
)
def test_first_bad_version(n, bad, expected, monkeypatch):
    import leetcode_top_easy_05_sorting_and_searching_02_first_bad_version as mod

    def fake_isBadVersion(version):
        return version >= bad

    monkeypatch.setattr(mod, "isBadVersion", fake_isBadVersion)
    assert mod.Solution().firstBadVersion(n) == expected

Comment my solution¶

Good:

correct binary search idea
updates bounds correctly
works on the provided cases

Can be improved:

first_bad_v is not needed
while (max_v - min_v) >= 0: is harder to read than while left < right
names like min_v and max_v are less standard than left and right

def isBadVersion(version):
    pass

class Solution:
    def firstBadVersion(self, n: int) -> int:
        first_bad_v = 1
        min_v = 1
        max_v = n
        while (max_v - min_v) >= 0:
            v = min_v + (max_v - min_v) // 2
            if isBadVersion(v):
                first_bad_v = v
                max_v = v - 1
            else:
                min_v = v + 1
        return first_bad_v

import pytest
import leetcode_top_easy_05_sorting_and_searching_02_first_bad_version as mod

@pytest.mark.parametrize(
    ("version_fails", "first_bad_v"),
    [
        ([True], 1),
        ([False, False, True, True, True], 3),
        ([False, True, True, True, True], 2),
        ([False, True, True, True], 2),
        ([False, False, True], 3),
    ]
)
def test_firstBadVersion(version_fails, first_bad_v, monkeypatch):
    def fake_isBadVersion(version):
        return version_fails[version - 1]

    monkeypatch.setattr(mod, "isBadVersion", fake_isBadVersion)
    assert Solution().firstBadVersion(len(version_fails)) == first_bad_v

A simpler version is:

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

Code¶

import pytest


# The API is provided by the platform.
def isBadVersion(version: int) -> bool:
    raise NotImplementedError


class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n

        # Binary search for the first version where isBadVersion(version) is True.
        while left < right:
            mid = left + (right - left) // 2

            if isBadVersion(mid):
                # mid may be the first bad version, keep it.
                right = mid
            else:
                # mid is good, so first bad is strictly to the right.
                left = mid + 1

        return left


@pytest.mark.parametrize(
    ("n", "bad", "expected"),
    [
        (1, 1, 1),
        (2, 1, 1),
        (2, 2, 2),
        (5, 4, 4),
        (5, 1, 1),
        (5, 5, 5),
        (8, 3, 3),
        (10, 7, 7),
    ],
)
def test_first_bad_version(n, bad, expected, monkeypatch):
    import leetcode_top_easy_05_sorting_and_searching_02_first_bad_version as mod

    def fake_isBadVersion(version):
        return version >= bad

    monkeypatch.setattr(mod, "isBadVersion", fake_isBadVersion)
    assert mod.Solution().firstBadVersion(n) == expected


# Interactive examples:
#
# n=5, bad=4
# states: [False, False, False, True, True]
# answer: 4
#
# n=1, bad=1
# states: [True]
# answer: 1