What is the time and space complexity of First Bad Version?

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

First Bad Version

Easy

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: First Bad Version

Approach

Check the middle version. If it is bad, the first bad version is at mid or earlier, so move right bound left. If good, move left bound right. Continue until pointers meet.

Complexity Analysis

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

Pattern

Binary Search (Boundary Finding)

Why It Works

The answer space is monotonic: bad is false then true and never reverts. Binary search finds the first true by keeping a shrinking interval where the first bad still exists.

Updated Feb 2026