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.

#278

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n] ，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool…

二分查找交互

题目描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

提示：

1 <= bad <= n <= 2³¹ - 1

lightbulb

解题思路

方法一：二分查找

我们定义二分查找的左边界 $l = 1$ ，右边界 $r = n$ 。

当 $l < r$ 时，我们计算中间位置 $\textit{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor$ ，然后调用 isBadVersion(mid) 接口，如果返回 $\textit{true}$ ，则说明第一个错误的版本在 $[l, \textit{mid}]$ 之间，我们令 $r = \textit{mid}$ ；否则第一个错误的版本在 $[\textit{mid} + 1, r]$ 之间，我们令 $l = \textit{mid} + 1$ 。

最终返回 $l$ 即可。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# 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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#374 猜数字大小 #1095 山脉数组中查找目标值 #1237 找出给定方程的正整数解