278. First Bad Version

Problem Description

You're managing a product with multiple versions numbered from 1 to n. Each new version is built on top of the previous one. Unfortunately, one of the versions has a bug, and since each version depends on the previous one, all versions after the bad version are also bad.

Your task is to find the first bad version that caused all subsequent versions to fail.

You have access to an API function isBadVersion(version) that returns:

true if the given version is bad
false if the given version is good

The goal is to identify the first bad version while minimizing the number of API calls.

For example, if you have 5 versions [1, 2, 3, 4, 5] and version 3 is the first bad one, then:

isBadVersion(1) returns false
isBadVersion(2) returns false
isBadVersion(3) returns true
isBadVersion(4) returns true
isBadVersion(5) returns true

You need to implement a function firstBadVersion(n) that returns the version number of the first bad version.

The key challenge is to find this version efficiently without checking every single version sequentially, as the number of versions n could be very large.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Since we have versions arranged in order from 1 to n, and we know that once a version is bad, all subsequent versions are also bad, this creates a clear pattern: there's a point where the versions transition from good to bad.

The versions look something like this: [good, good, good, bad, bad, bad]. We need to find where this transition happens.

If we check versions one by one from the beginning, we might need to make up to n API calls in the worst case. This would be inefficient for large values of n.

However, we can take advantage of the sorted nature of the problem. When we check any version in the middle:

If it's bad, we know the first bad version must be either this one or somewhere before it
If it's good, we know the first bad version must be somewhere after it

This insight allows us to eliminate half of the search space with each check, similar to how we search for a word in a dictionary - we don't read every page, we open to the middle and determine which half contains our target.

By repeatedly checking the middle version and narrowing down our search range based on whether it's good or bad, we can find the first bad version in O(log n) API calls instead of O(n). This is the essence of binary search - we maintain a range where we know the first bad version exists, and keep cutting this range in half until we pinpoint the exact version.

The key observation is that we're looking for the boundary between good and bad versions, and binary search is perfect for finding boundaries in sorted sequences.

Solution Approach

We implement binary search to find the first bad version efficiently. Here's how the algorithm works:

Initialize boundaries: Set the left boundary l = 1 (first version) and right boundary r = n (last version). These boundaries represent the range where the first bad version could exist.
Binary search loop: While l < r, we haven't narrowed down to a single version yet:
- Calculate the middle position: mid = (l + r) >> 1 (using right shift by 1 bit, which is equivalent to dividing by 2)
- Call isBadVersion(mid) to check if the middle version is bad
Adjust search range based on the result:
- If isBadVersion(mid) returns true: The middle version is bad, which means the first bad version is either at position mid or somewhere before it. We update r = mid to search in the left half, keeping mid as a potential answer.
- If isBadVersion(mid) returns false: The middle version is good, so the first bad version must be after it. We update l = mid + 1 to search in the right half.
Return the result: When the loop ends (l == r), we've found the exact position of the first bad version. Return l.

The key insight in the boundary updates is:

When we find a bad version, we include it in our search range (r = mid) because it could be the first bad version
When we find a good version, we exclude it from our search range (l = mid + 1) because we know the first bad version must come after it

This approach guarantees we'll find the first bad version in O(log n) time complexity, making at most ⌈log₂(n)⌉ API calls, which is optimal for this problem.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through finding the first bad version when n = 8 and version 5 is the first bad one.

Initial setup: versions [1, 2, 3, 4, 5, 6, 7, 8] where versions 1-4 are good (G) and 5-8 are bad (B).

Step 1: Initialize boundaries

l = 1, r = 8
Search range: [1, 2, 3, 4, 5, 6, 7, 8]

Step 2: First iteration

Calculate middle: mid = (1 + 8) >> 1 = 4
Call isBadVersion(4) → returns false (version 4 is good)
Since version 4 is good, the first bad version must be after it
Update: l = mid + 1 = 5
New search range: [5, 6, 7, 8]

Step 3: Second iteration

l = 5, r = 8
Calculate middle: mid = (5 + 8) >> 1 = 6
Call isBadVersion(6) → returns true (version 6 is bad)
Since version 6 is bad, the first bad version is either 6 or before it
Update: r = mid = 6
New search range: [5, 6]

Step 4: Third iteration

l = 5, r = 6
Calculate middle: mid = (5 + 6) >> 1 = 5
Call isBadVersion(5) → returns true (version 5 is bad)
Since version 5 is bad, the first bad version is either 5 or before it
Update: r = mid = 5
New search range: [5]

Step 5: Loop terminates

Now l = 5 and r = 5 (they're equal)
Return l = 5

We found the first bad version (5) with only 3 API calls instead of checking all 8 versions sequentially. Each API call eliminated roughly half of the remaining search space, demonstrating the efficiency of binary search.

Solution Implementation

1# The isBadVersion API is already defined for you.
2# def isBadVersion(version: int) -> bool:
3
4
5class Solution:
6    def firstBadVersion(self, n: int) -> int:
7        """
8        Find the first bad version using binary search.
9      
10        Args:
11            n: Total number of versions
12          
13        Returns:
14            The first bad version number
15        """
16        # Initialize search boundaries
17        left, right = 1, n
18      
19        # Binary search to find the first bad version
20        while left < right:
21            # Calculate middle point using bit shift to avoid overflow
22            # (left + right) >> 1 is equivalent to (left + right) // 2
23            middle = (left + right) >> 1
24          
25            # If middle version is bad, the first bad version is at middle or before
26            if isBadVersion(middle):
27                right = middle
28            # If middle version is good, the first bad version is after middle
29            else:
30                left = middle + 1
31      
32        # When left == right, we've found the first bad version
33        return left
34

1/* The isBadVersion API is defined in the parent class VersionControl.
2      boolean isBadVersion(int version); */
3
4public class Solution extends VersionControl {
5    /**
6     * Finds the first bad version using binary search.
7     * Given n versions [1, 2, ..., n], find the first bad version.
8     * All versions after a bad version are also bad.
9     * 
10     * @param n The total number of versions
11     * @return The first bad version number
12     */
13    public int firstBadVersion(int n) {
14        // Initialize binary search boundaries
15        // left starts at version 1 (minimum version)
16        int left = 1;
17        // right starts at version n (maximum version)
18        int right = n;
19      
20        // Continue searching while search space has more than one element
21        while (left < right) {
22            // Calculate middle point using unsigned right shift to avoid overflow
23            // This is equivalent to (left + right) / 2 but prevents integer overflow
24            int middle = (left + right) >>> 1;
25          
26            // Check if the middle version is bad
27            if (isBadVersion(middle)) {
28                // If middle is bad, the first bad version is at middle or before it
29                // Move right boundary to middle (keep middle in search space)
30                right = middle;
31            } else {
32                // If middle is good, the first bad version must be after it
33                // Move left boundary to middle + 1 (exclude middle from search space)
34                left = middle + 1;
35            }
36        }
37      
38        // When left == right, we've found the first bad version
39        return left;
40    }
41}
42

1// The API isBadVersion is defined for you.
2// bool isBadVersion(int version);
3
4class Solution {
5public:
6    int firstBadVersion(int n) {
7        // Initialize binary search boundaries
8        // left starts at version 1, right starts at version n
9        int left = 1;
10        int right = n;
11      
12        // Binary search to find the first bad version
13        while (left < right) {
14            // Calculate middle point avoiding integer overflow
15            // Using left + (right - left) / 2 instead of (left + right) / 2
16            int middle = left + (right - left) / 2;
17          
18            // Check if the middle version is bad
19            if (isBadVersion(middle)) {
20                // If bad, the first bad version is at middle or before it
21                // Move right boundary to middle (inclusive)
22                right = middle;
23            } else {
24                // If good, the first bad version must be after middle
25                // Move left boundary to middle + 1
26                left = middle + 1;
27            }
28        }
29      
30        // When left == right, we've found the first bad version
31        return left;
32    }
33};
34

1/**
2 * The isBadVersion API is defined in the parent class Relation.
3 * isBadVersion(version: number): boolean {
4 *     ...
5 * };
6 */
7
8/**
9 * Binary search solution to find the first bad version
10 * Uses a higher-order function pattern to create a closure with the isBadVersion API
11 * 
12 * @param isBadVersion - API function to check if a version is bad
13 * @returns A function that finds the first bad version given the total number of versions
14 */
15const solution = function (isBadVersion: (version: number) => boolean): (n: number) => number {
16    /**
17     * Finds the first bad version using binary search
18     * 
19     * @param n - Total number of versions
20     * @returns The first bad version number
21     */
22    return function (n: number): number {
23        // Initialize binary search boundaries
24        // left starts at 1 (first version), right starts at n (last version)
25        let left: number = 1;
26        let right: number = n;
27      
28        // Continue binary search while search space has more than one element
29        while (left < right) {
30            // Calculate middle point using unsigned right shift to avoid overflow
31            // >>> 1 is equivalent to Math.floor(division by 2)
32            const middle: number = (left + right) >>> 1;
33          
34            // If middle version is bad, the first bad version is at middle or before
35            if (isBadVersion(middle)) {
36                right = middle;  // Include middle in search space
37            } else {
38                // If middle version is good, the first bad version is after middle
39                left = middle + 1;  // Exclude middle from search space
40            }
41        }
42      
43        // When left === right, we've found the first bad version
44        return left;
45    };
46};
47

Time and Space Complexity

The time complexity is O(log n), where n is the input parameter representing the total number of versions. This is because the algorithm uses binary search, which repeatedly divides the search space in half. In each iteration, the algorithm eliminates half of the remaining search space by checking the middle element with isBadVersion(mid). The number of iterations required is logarithmic with respect to n, specifically ⌈log₂(n)⌉ iterations in the worst case.

The space complexity is O(1), as the algorithm only uses a constant amount of extra space. The variables l, r, and mid are the only additional memory allocations, and they don't depend on the size of the input n. The algorithm operates in-place without using any recursive calls or additional data structures that would scale with the input size.

Common Pitfalls

1. Integer Overflow in Middle Calculation

The Pitfall: When calculating the middle point using mid = (left + right) // 2, if both left and right are very large integers, their sum could exceed the maximum integer value, causing overflow issues in some programming languages (though Python handles big integers automatically).

Solution: Use the formula mid = left + (right - left) // 2 or bit manipulation mid = (left + right) >> 1. The bit shift approach works well in Python, but the safer universal formula is:

middle = left + (right - left) // 2

2. Incorrect Boundary Updates

The Pitfall: A common mistake is updating boundaries incorrectly:

Setting right = mid - 1 when isBadVersion(mid) is true would skip checking if mid itself is the first bad version
Setting left = mid when isBadVersion(mid) is false would cause an infinite loop when left = right - 1 and mid = left

Solution: Always remember the logic:

When you find a bad version, keep it in the search range: right = mid
When you find a good version, exclude it from the search range: left = mid + 1

3. Off-by-One Errors with Loop Condition

The Pitfall: Using while left <= right instead of while left < right would require additional logic to determine which value to return, and could lead to unnecessary extra API calls.

Solution: Use while left < right and return left when the loop ends. This ensures that when left == right, you've converged on the exact answer without ambiguity.

4. Starting Search from Wrong Indices

The Pitfall: Starting with left = 0 instead of left = 1, forgetting that versions are numbered from 1 to n, not 0 to n-1.

Solution: Always initialize with left = 1, right = n to match the problem's version numbering system.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: