#278

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

First Bad Version

Find the first bad version of a product using binary search, minimizing the number of API calls.

Problem Statement

You are tasked with identifying the first bad version of a product in a sequence of versions, where every version after a bad version is also bad. Given n versions, the goal is to minimize the number of calls to an API function isBadVersion(version) to find the first version that fails the quality check.

The problem requires an efficient algorithm using binary search, where you repeatedly narrow down the search space by checking versions in the middle of the remaining range. You must ensure that your solution is optimal in terms of minimizing the number of calls to isBadVersion.

Examples

Example 1

Input: n = 5, bad = 4

Output: 4

call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version.

Example 2

Input: n = 1, bad = 1

Output: 1

Example details omitted.

Constraints

1 <= bad <= n <= 231 - 1

Solution Approach

Binary Search Over the Valid Answer Space

Start by initializing the search range to cover all versions, from 1 to n. Use binary search to iteratively check the middle version of the current range. If the middle version is bad, narrow the search to the left half; if it's not, narrow the search to the right half.

Minimizing API Calls

Each call to isBadVersion reduces the search space, so by halving the space at each step, the number of calls is minimized. This is a key advantage of binary search, as it allows you to find the first bad version in logarithmic time.

Handling Edge Cases

Consider edge cases such as when n equals 1 or when the first version is bad. Ensure that the binary search handles these cases correctly without causing out-of-bounds errors or unnecessary API calls.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(log n) due to the binary search approach. The space complexity is O(1) as no additional space is required beyond the variables used for searching.

What Interviewers Usually Probe

Candidate demonstrates a clear understanding of binary search and its application to minimizing API calls.
Candidate correctly handles edge cases, such as n = 1 or when the first version is bad.
Candidate provides an optimal solution with minimal API calls, showcasing efficiency in problem-solving.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution by not using binary search, leading to inefficient solutions.
Failing to handle edge cases such as when the first version is bad.
Incorrectly adjusting the search bounds, which may result in out-of-bounds errors or infinite loops.

Follow-up variants

Implementing the solution iteratively instead of recursively.
Modifying the algorithm to handle versions that can be accessed in batches instead of individually.
Extending the problem to handle additional constraints, such as multiple bad versions or dynamic version updates.

FAQ

What is the optimal time complexity for solving the First Bad Version problem?

The optimal time complexity is O(log n) due to the binary search approach, which minimizes the number of API calls.

How can I minimize the number of API calls in this problem?

By using binary search, you can halve the search space with each API call, minimizing the total number of calls.

What should I do if the first version is bad?

Ensure that your binary search handles the case where the first version is bad by properly adjusting the search bounds.

Can this problem be solved with a linear search?

A linear search would work but would be inefficient. Binary search is the optimal solution because it reduces the search space logarithmically.

What happens if n equals 1 in the First Bad Version problem?

If n equals 1, the only version is the bad one, so the solution will immediately identify it as the first bad version.

terminal

Solution

Solution 1: Binary Search

We define the left boundary of the binary search as $l = 1$ and the right boundary as $r = n$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:


class Solution:
    def firstBadVersion(self, n: int) -> int:
        l, r = 1, n
        while l < r:
            mid = (l + r) >> 1
            if isBadVersion(mid):
                r = mid
            else:
                l = mid + 1
        return l

Continue Practicing

#374 guess number higher or lower #1095 find in mountain array #1237 find positive integer solution for a given equation