Leetcode May Challenge – 05/01: First Bad Version(Python)

题目描述 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 versio 在LeetCode五月挑战的首日问题“First Bad Version”中，你被设定为一名产品经理，你的团队正在开发一款新产品。不幸的是，最新的版本未能通过质量检查。由于每个新版本都是基于旧版本构建的，一旦有一个版本出现问题，后续的所有版本都将受到影响。 给定一个API `isBadVersion(version)`，它可以返回版本`version`是否为坏版本，返回值为布尔类型（True或False）。你的任务是编写一个函数`firstBadVersion(n)`，找出导致所有后续版本都变坏的第一个坏版本。目标是尽量减少调用API的次数。 ### 解决方案 #### 暴力解法： 最直接的方法是从版本1开始，逐个调用`isBadVersion()`，直到找到第一个返回True的版本。这种方法的时间复杂度为O(n)，因为可能需要检查所有n个版本。 #### 二分查找法（Binary Search）： 二分查找法可以显著减少API调用次数。设置左右边界，`left`为1，`right`为`n`，并初始化一个变量`first_bad_version`来记录第一个坏版本，初始值设为-1。接下来，进入循环，只要`left`不大于`right`，就持续执行以下步骤： 1. 计算中间版本`mid`，即`(left + right) // 2`。 2. 调用`isBadVersion(mid)`，如果返回True，说明`mid`是坏版本，更新`first_bad_version`为`mid`，并将右边界`right`移动到`mid - 1`，因为坏版本可能出现在`mid`的左侧。 3. 如果`isBadVersion(mid)`返回False，说明坏版本在`mid`的右侧，将左边界`left`更新为`mid + 1`。 当`left`超过`right`时，循环结束，返回`first_bad_version`作为结果。这种方法的时间复杂度为O(log n)，因为每次循环都将搜索范围减半。 下面是使用二分查找法的Python代码实现： ```python class Solution: def firstBadVersion(self, n): """Given n, find the first bad version. :type n: int :rtype: int """ left = 1 right = n first_bad_version = -1 while left <= right: mid = (left + right) // 2 if isBadVersion(mid): first_bad_version = mid right = mid - 1 else: left = mid + 1 return first_bad_version ``` 在这个问题中，二分查找法的效率比暴力解法高得多，尤其是在版本数量非常大的情况下。因此，对于这种类型的问题，优先考虑使用二分查找或其他高效的搜索策略来解决。在实际编程挑战或面试中，展示这种优化问题解决能力是非常重要的。