First Bad Version

Easy Binary Search Unique 1-D Binary Search Original on LeetCode

First Bad Version is a easy binary search problem solved with the unique 1-d binary search pattern. The best approach, optimal (first true with binary search), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from linear scan up.

Problem

You have versions 1..n of a product. Once a version is bad, every version after it is bad too. Using an API isBadVersion(v), find the first bad version while making as few calls as possible.

Examples

Example 1

Input
n = 6, first bad = 4
Output
4
Why
isBadVersion(3) = false, isBadVersion(4) = true.

Example 2

Input
n = 1, first bad = 1
Output
1

Constraints

  • 1 <= bad <= n <= 2^31 - 1
  • Minimise calls to isBadVersion.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 4 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Linear scanO(n)O(1)
Optimal (first true with binary search)O(log n)O(1)

1Linear scan

TimeO(n)
SpaceO(1)

Call isBadVersion from 1 upward and return the first true.

  1. for v = 1..n: if isBadVersion(v) return v.
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        for (int v = 1; v < n; v++) if (isBadVersion(v)) return v;
        return n;
    }
}

Edge cases to test

  • n near 2^31 - 1 (lo + hi overflows)
  • The first version is bad

Hints

Hint 1

The answers look like false, false, ..., true, true: find the first true.

FAQ

What is the best time complexity for First Bad Version?

Optimal (first true with binary search) runs in O(log n) time and O(1) extra space.

Which pattern does First Bad Version use?

It is a binary search problem that uses the unique 1-d binary search pattern. Other problems with the same pattern: Single Element in a Sorted Array, Find Peak Element.

Is there a brute force solution for First Bad Version?

Yes. Linear scan takes O(n) time and O(1) space. Call isBadVersion from 1 upward and return the first true.

Which edge cases should I test for First Bad Version?

n near 2^31 - 1 (lo + hi overflows); The first version is bad.