First Bad Version

easy

Given a version control system where all versions after a bad version are bad, find the first bad version

First Bad Version

Key Insight

Binary search the version space and keep the earliest index where isBadVersion(mid) is true.

Step 1Initialize
False ... false ... true ... true
L
R
1
0
2
1
3
2
4
3
5
4
6
5
7
6
Search space: [0..6]

Versions 1..n, with all good versions before the first bad version.

1 / 4

Learn the Pattern

Binary SearchEliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
Practice the Code

Step-by-Step Walkthrough: First Bad Version

Binary search the version space and keep the earliest index where isBadVersion(mid) is true.

  1. Initialize

    Versions 1..n, with all good versions before the first bad version.

  2. First Mid Check

    mid=3, isBadVersion(4)=true, so first bad is at 4 or earlier.

  3. Second Check

    mid=1, isBadVersion(2)=false, so first bad is after 2.

  4. Converge

    left and right meet at first bad version index.