LeetCode: 278 First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

问题

你是一名产品经理，目前正在领导一个团队开发新产品。不幸的是，最新版本未能通过质量检查。由于每个版本都是基于前一个版本开发的，因此在一个坏版本之后的所有版本都是坏的。

假设你有 n 个版本 [1, 2, …, n]，你想找出第一个导致所有后续版本都坏掉的坏版本。

给定一个 API bool isBadVersion(version)，它返回 version 是否为坏版本。实现一个函数来查找第一个坏版本。你应该尽量减少对 API 的调用次数。

解决方案

二分查找法

Approach: Binary Search / 二分查找法

This approach utilizes binary search to efficiently identify the first bad version. By narrowing down the search space with each iteration, the solution minimizes the number of API calls, achieving O(log n) time complexity.

这种方法利用二分查找来高效地识别第一个坏版本。通过在每次迭代中缩小搜索空间，该解决方案将 API 调用次数最小化，实现了 O(log n) 时间复杂度。

Implementation / 实现

Python

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

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

Explanation / 解释

Initialize Pointers / 初始化指针
```
left, right = 1, n
```
- English: We initialize two pointers, left and right, to represent the search space between the first version and the last version.
- Chinese: 我们初始化两个指针，left 和 right，表示从第一个版本到最后一个版本的搜索空间。
Binary Search Loop / 二分查找循环
```
while left < right:
   mid = left + (right - left) // 2
```
- English: We use a binary search loop to repeatedly narrow down the search space by finding the middle point mid.
- Chinese: 我们使用二分查找循环，通过找到中点 mid，反复缩小搜索空间。
Check Midpoint Version / 检查中点版本
```
if isBadVersion(mid):
   right = mid
else:
   left = mid + 1
```
- English: If mid is a bad version, then the first bad version must be at mid or earlier, so we set right = mid. Otherwise, it must be after mid, so we set left = mid + 1.
- Chinese: 如果 mid 是坏版本，那么第一个坏版本必须在 mid 或更早的位置，因此我们设置 right = mid。否则，它必须在 mid 之后，因此我们设置 left = mid + 1。
Return the First Bad Version / 返回第一个坏版本
```
return left
```
- English: When the loop exits, left will be pointing to the first bad version, so we return left.
- Chinese: 当循环退出时，left 将指向第一个坏版本，因此我们返回 left。

Recursive Approach / 递归方法

A recursive approach could also be applied here, using a similar logic to binary search, but it's generally less efficient due to function call overhead and stack space usage.

递归方法也可以在这里应用，使用类似于二分查找的逻辑，但由于函数调用的开销和堆栈空间的使用，它通常效率较低。

Recursive Implementation / 递归实现

class Solution:
    def firstBadVersion(self, n: int) -> int:
        return self.binarySearch(1, n)

    def binarySearch(self, left, right):
        if left == right:
            return left
        mid = left + (right - left) // 2
        if isBadVersion(mid):
            return self.binarySearch(left, mid)
        else:
            return self.binarySearch(mid + 1, right)

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(log n), because we are performing a binary search.
Space Complexity / 空间复杂度: O(1) for the iterative approach, and O(log n) for the recursive approach due to the recursion stack.

Key Concept / 关键概念

Binary Search / 二分查找: This technique efficiently finds the first bad version by repeatedly dividing the search space in half, minimizing the number of API calls.
二分查找: 这种技术通过反复将搜索空间减半，最小化 API 调用次数，从而高效地找到第一个坏版本。

Summary / 总结

English: The binary search method is ideal for problems where the search space is ordered, and you need to find the first occurrence of a condition.
Chinese: 二分查找法非常适合用于搜索空间有序，且需要找到某个条件第一次出现的位置的问题。

Tips / 提示

English: Practice binary search on a variety of problems to get comfortable with its application in different contexts, especially in ordered data sets.
Chinese: 在各种问题中练习二分查找，以熟悉它在不同上下文中的应用，尤其是在有序数据集中的应用。

Solution Template for Similar Questions / 提示

English: Whenever you're asked to find the first occurrence of something in an ordered set, consider using binary search.
Chinese: 每当需要在有序集中找到某个条件第一次出现的位置时，考虑使用二分查找。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice problems that involve binary search to build a strong understanding of how to effectively search in ordered data sets.
Chinese: 练习涉及二分查找的问题，以建立对如何在有序数据集中有效搜索的深刻理解。

Post Views: 16

CODEBITWAVE

LeetCode: 278 First Bad Version