← DSA Atlas
Dedicated problem page · #278

First Bad Version

EasyBinary SearchBinary search for the first trueBinary search on a monotonic predicate
Solve on LeetCode ↗
278
EasyBinary SearchBinary search on a monotonic predicateBinary search for the first true

First Bad Version

You manage n versions [1..n]. After some version every later version is bad. Given an API isBadVersion(version) that returns whether a version is bad, find the first bad version while minimizing the number of API calls.

Open official problem prompt ↗
In plain English

Find the exact version where quality flips from good to bad using as few probes as possible.

Picture it like this

A row of light bulbs off then on. You want the first lit bulb. Instead of checking each, you test the middle: if it is on the switch is at or before it, if off the switch is later.

Example
Input
n = 5, first bad version = 4
Output
4
Why
Versions 1-3 are good and versions 4-5 are bad, so 4 is the first bad one.
Constraints
1 <= bad <= n <= 2^31 - 1isBadVersion returns a booleanOnce a version is bad, all following versions are badMinimize calls to the API
Pattern lesson

See the pattern, then code

Binary search for the first true
Recognition clue

A monotonic good-then-bad boundary plus 'minimize checks' is the classic first-true binary search; the predicate flips exactly once.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. isBadVersion is false for a prefix and true for the rest, so you binary-search the flip point: pull hi down onto any bad version and push lo up past good ones until they meet.

New words, made simpleKnow these before the algorithm
Monotonic predicate
A yes/no test that, once true, stays true for all larger inputs
Boundary
The single point where the predicate changes value
Lower bound search
Binary search that returns the first index satisfying the predicate
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Linear probe

Far too many API calls for large n.

Call isBadVersion on 1, 2, 3, ... until it returns true.

Time O(n)Space O(1)
Best choiceFirst-true binary search

Minimizes API calls and handles n up to 2^31 - 1.

Halve the range each step, moving hi onto bad versions and lo past good ones.

Time O(log n)Space O(1)
The rule we keep true

Invariant

The first bad version always lies within [lo, hi]: everything below lo is good and hi is always a bad version (or the initial n).

Why this is correct

Reasoning

Because badness is monotonic, a bad mid means no earlier-or-equal bad version is excluded when we set hi = mid, and a good mid means the answer is strictly after mid, so lo = mid + 1 is safe. Each step halves the range, and when lo == hi that index is the first bad version.

The algorithm in three movesSay these aloud before coding
1Set lo = 1 and hi = n

lo=1 hi=5 mid=3 good -> lo=4

2Compute mid without overflow

lo=4 hi=5 mid=4 bad -> hi=4

3If isBadVersion(mid), the answer is mid or earlier, so hi = mid

lo==hi=4 -> answer 4

4Otherwise the first bad is later, so lo = mid + 1

5Return lo when lo == hi

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
1:good0
2:good1
3:good2
4:bad3
5:bad4
1 · Readlo=1, hi=5
2 · AskIs version 3 bad?
3 · Update statemid=3, good
4 · ResultFirst bad is later, lo = 4
Key takeaway

The search brackets the good/bad boundary and settles on version 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6Bracket all versions

    The answer is somewhere in [1, n].

  2. 2
    Lines 8Overflow-safe midpoint

    lo + (hi - lo) // 2 avoids overflow for very large n.

  3. 3
    Lines 9-12Move toward the boundary

    Bad keeps mid (hi = mid); good discards mid (lo = mid + 1).

  4. 4
    Lines 13Return the flip point

    lo equals the first bad version.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • The very first version is bad (answer 1)
  • Only the last version is bad (answer n)
  • n = 1
  • Huge n near 2^31 - 1 where naive mid = (lo+hi)/2 could overflow in fixed-width languages
!

Common beginner mistakes

  • Setting hi = mid - 1, which can skip the true first bad version
  • Using lo <= hi with hi = mid, causing an infinite loop
  • Computing mid as (lo + hi) // 2 in languages where that overflows
Check your understanding

Why set hi = mid rather than hi = mid - 1 when isBadVersion(mid) is true?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search