How do you approach First Bad Version?

The versions form a monotonic sequence of good values followed by bad ones - exactly the shape binary search needs.

What is the time complexity of First Bad Version?

Time complexity: O(log n) tests.. Space complexity: O(1).

What are common mistakes on First Bad Version?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

First Bad Version

EasyAlgorithms

Description

Versions 1 through n were released in order. At some point a bad version was shipped, and every version after it is also bad.

You can test whether a version is bad. Find the first bad one using as few tests as possible.

Implement firstBadVersion(n, firstBad), where firstBad is the answer the testing API would reveal - treat version v as bad exactly when v >= firstBad. Return the first bad version.

Example 1

Input: n = 5, firstBad = 4

Output: 4

Example 2

Input: n = 1, firstBad = 1

Output: 1

Example 3

Input: n = 100, firstBad = 1

Output: 1

Constraints

- 1 <= firstBad <= n <= 2^31 - 1 - The badness property is monotonic: once bad, always bad. - Minimize the number of version tests - O(log n).

First Bad Version: approach, complexity and pitfalls

An easy binary search problem, graded against 6 test cases (3 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

If you are stuck

Show the 3-step hint ladder

The versions form a monotonic sequence of good values followed by bad ones - exactly the shape binary search needs.
Search for the BOUNDARY, not for a value: narrow to the first version that tests bad.
When a version is bad, it might itself be the answer, so set hi = mid rather than mid - 1. Otherwise you can skip past it.

The optimal approach

Show the approach: Binary search on a predicate, not on values

This is the canonical example of binary searching a monotonic predicate. There is no sorted array to look at - only a yes/no test - but the answers form the pattern `false false ... false true ... true`, and that is all binary search needs.

Search for the boundary: while `lo < hi`, test the midpoint. If it is bad, the first bad version is at `mid` or earlier, so set `hi = mid` - crucially not `mid - 1`, which could step over the answer. If it is good, the boundary is strictly after, so `lo = mid + 1`. When they meet, that is the first bad version.

Overflow is a real hazard here rather than a theoretical one, since `n` can be 2^31 - 1: `(lo + hi) / 2` overflows a 32-bit int in the very first iteration for large ranges. Use `lo + (hi - lo) / 2`. (JavaScript and Python are immune, but the interviewer will usually ask.)

The general lesson transfers widely: any problem where a boolean condition flips exactly once across a range - minimum capacity to ship in D days, smallest divisor under a threshold - is a binary search, even when nothing is sorted.

Time: O(log n) tests.
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

← Back to problems

First Bad Version

EasyAlgorithms

Description

Versions 1 through n were released in order. At some point a bad version was shipped, and every version after it is also bad.

You can test whether a version is bad. Find the first bad one using as few tests as possible.

Implement firstBadVersion(n, firstBad), where firstBad is the answer the testing API would reveal - treat version v as bad exactly when v >= firstBad. Return the first bad version.

Example 1

Input: n = 5, firstBad = 4

Output: 4

Example 2

Input: n = 1, firstBad = 1

Output: 1

Example 3

Input: n = 100, firstBad = 1

Output: 1

Constraints

- 1 <= firstBad <= n <= 2^31 - 1 - The badness property is monotonic: once bad, always bad. - Minimize the number of version tests - O(log n).

First Bad Version: approach, complexity and pitfalls

An easy binary search problem, graded against 6 test cases (3 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

If you are stuck

Show the 3-step hint ladder

The versions form a monotonic sequence of good values followed by bad ones - exactly the shape binary search needs.
Search for the BOUNDARY, not for a value: narrow to the first version that tests bad.
When a version is bad, it might itself be the answer, so set hi = mid rather than mid - 1. Otherwise you can skip past it.

The optimal approach

Show the approach: Binary search on a predicate, not on values

Time: O(log n) tests.
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.