278. First Bad Version

On LeetCode ->

Problem¶

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

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 is it interesting?¶

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

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

Python solution¶

class Solution:
    def firstBadVersion(self, n: int) -> int:
        l, r = 1, n

        while l <= r:
            mid = (l + r) // 2

            if isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1

        return l

Comment on 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