How do you solve First Bad Version?

Initialize two pointers, left = 1 and right = n. While left < right, compute mid = (left + right) // 2. If isBadVersion(mid) is True, move right to mid; else move left to mid + 1. When left equals right, return left as the first bad version.

First Bad Version

Q: What is the time complexity of First Bad Version?

O(log n). Each iteration halves the search space by moving either left or right pointer, resulting in logarithmic time relative to n.

Q: What pattern does First Bad Version use?

The Pattern: Modified Binary Search (Boundary Search) The Heuristic: When searching for a boundary or transition point in a monotonic predicate over a sorted domain, use binary search to repeatedly halve the search space by testing the midpoint and adjusting boundaries accordingly.

Easy Modified Binary Search

Problem

Given n versions [1, 2, ..., n] and an API isBadVersion(version) that returns whether a version is bad, return the first bad version such that all versions after it are bad.

1 ≤ n ≤ 2³¹ - 1
The isBadVersion API is monotonic: if version x is bad, then all versions > x are bad.

Example

Input: n = 5

Output: 4

Versions 1, 2, and 3 are good, while versions 4 and 5 are bad. The algorithm uses binary search to efficiently narrow down the first bad version. Starting with left=1 and right=5, it checks mid=3. Since version 3 is good, it moves left to 4. Then it checks mid=4, which is bad, so it moves right to 4. When left equals right, it returns 4 as the first bad version.

Approach

Straightforward Solution

A naive approach would check each version sequentially from 1 to n, calling isBadVersion until the first bad version is found. This approach is O(n) and inefficient for large n.

Core Observation

The problem reduces to finding the boundary point in a monotonic boolean sequence where values switch from False (good) to True (bad). This boundary search is a classic use case for binary search.

Path to Optimal

Preview

Recognizing the monotonic property of isBadVersion, binary search can be applied to find the transition point efficiently. By repeatedly checking the middle version, the search space halves each iteration…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize two pointers, left = 1 and right = n. While left < right, compute mid = (left + right) // 2…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n)

Each iteration halves the search space by moving either left or right pointer, resulting in logarithmic time relative to n.

Space

O(1)

Only a fixed number of variables (left, right, mid) are used, regardless of input size.

Pattern Spotlight

Modified Binary Search (Boundary Search)

When searching for a boundary or transition point in a monotonic predicate over a sorted domain, use binary search to repeatedly halve the search space by testing the midpoint and adjusting boundaries accordingly.

Solution

Python

1class Solution:
2    def firstBadVersion(self, n: int) -> int:
3
4        left = 1
5        right = n
6
7        while left < right:
8
9            mid = (left + right) // 2
10
11            if isBadVersion(mid):
12                right = mid
13            else:
14                left = mid + 1
15
16        return left

Step-by-Step Solution

Initialize Search Boundaries to Cover All Versions

4left = 1
5right = n

Objective

To set the initial search range covering all versions from 1 to n.

Key Insight

Starting with left at 1 and right at n ensures the entire version range is considered. This setup is essential because the first bad version could be anywhere in this range, and the binary search will progressively narrow it down.

Interview Quick-Check

Core Logic

Setting left = 1 and right = n initializes the binary search boundaries to the full version range.

State & Boundaries

The search space is inclusive of both left and right pointers, ensuring no versions are skipped.

Iteratively Narrow Search Space Using Binary Search

To repeatedly halve the search space by checking the middle version and adjusting boundaries based on whether it is bad.

Return the Identified First Bad Version

To return the converged pointer as the first bad version after the search space is narrowed to one element.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 16 Critical

return left

Return the converged pointer as the first bad version.

When left equals right, the search space is a single version, which must be the first bad version due to the binary search narrowing.

Line 11 Critical

if isBadVersion(mid):

Check if the midpoint version is bad using the API.

This check determines which half of the search space contains the first bad version, leveraging the monotonic property of isBadVersion.

Line 12 Critical

right = mid

Move the right pointer to mid when the midpoint version is bad.

If mid is bad, the first bad version could be mid itself or an earlier version. Moving right to mid keeps mid inside the search space while eliminating later versions.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why does moving the right pointer to mid when isBadVersion(mid) is True guarantee that the first bad version is not missed?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct First Bad Version from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the First Bad Version drill

or drill a free problem

1	`class Solution:`
2	`def firstBadVersion(self, n: int) -> int:`
3
4	`left = 1`
5	`right = n`
6
7	`while left < right:`
8
9	`mid = (left + right) // 2`
10
11	`if isBadVersion(mid):`
12	`right = mid`
13	`else:`
14	`left = mid + 1`
15
16	`return left`