278.第一个错误版本
278.1 题目
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 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^31 - 1
278.2 题解
方法一：二分查找
思路
版本号是有序的，而且错误版本有连续性：第一个错误版本之后的所有版本都是错的。
这正好符合二分查找的场景：
- 如果 mid 是错误版本，说明第一个错误版本在左半边（包括 mid）
- 如果 mid 是正确版本，说明第一个错误版本在右半边
最终 left 会收敛到第一个错误版本。
举个例子：n=5, bad=4
- left=1, right=5, mid=3：isBadVersion(3)=false，left=4
- left=4, right=5, mid=4：isBadVersion(4)=true，right=4
- left=right=4，返回4
只调用了2次API！
复杂度分析
- 时间复杂度：
O(log n)，二分查找 - 空间复杂度：
O(1)
代码
// 方法一：二分查找
// 使用二分查找方法来寻找第一个错误的版本
static int FirstBadVersion1(int n, int bad)
{
// 初始化左边界为第一个版本号
int left = 1;
// 初始化右边界为最后一个版本号
int right = n;
// 当左边界小于右边界时进行循环
while (left < right)
{
// 计算中间版本号
int mid = left + (right - left) / 2;
// 如果中间版本号是错误的版本
if (IsBadVersion(mid))
{
// 将右边界移到中间版本号
right = mid;
}
else
{
// 如果中间版本号不是错误的版本，将左边界移到中间版本号的下一个版本
left = mid + 1;
}
}
// 返回左边界，即为第一个错误的版本
return left;
}
方法二：线性扫描
思路
从第一个版本开始依次检查，找到第一个错误的版本立即返回。
简单但效率低，会调用很多 API。
举个例子：n=5, bad=4
- isBadVersion(1)=false
- isBadVersion(2)=false
- isBadVersion(3)=false
- isBadVersion(4)=true，返回4
调用了4次API。
复杂度分析
- 时间复杂度：
O(n)，最坏情况遍历所有版本 - 空间复杂度：
O(1)
代码
```csharp
// 方法二：线性扫描
// 使用线性扫描方法来寻找第一个错误的版本
static int FirstBadVersion2(int n, int bad)
{
// 遍历所有版本号
for (int i = 1; i <= n; i++)
{
// 如果当前版本是错误的版本，返回该版本号
if (IsBadVersion(i))
{
return i;
}
}
// 如果没有找到错误的版本，返回-1
return -1; // Not reached, just to satisfy compiler
}
278.3 代码
using System;
class Program
{
static void Main()
{
#region 题目
// 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。
// 由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
// 假设你有 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^31 - 1
#endregion
#region 测试
// 示例 1
int n1 = 5;
int bad1 = 4;
int result1_1 = FirstBadVersion1(n1, bad1);
Console.WriteLine($"示例1 方法1 输出：{result1_1}");
int result1_2 = FirstBadVersion2(n1, bad1);
Console.WriteLine($"示例1 方法2 输出：{result1_2}");
// 示例 2
int n2 = 1;
int bad2 = 1;
int result2_1 = FirstBadVersion1(n2, bad2);
Console.WriteLine($"示例2 方法1 输出：{result2_1}");
int result2_2 = FirstBadVersion2(n2, bad2);
Console.WriteLine($"示例2 方法2 输出：{result2_2}");
#endregion
}
#region 答案
// 方法一：二分查找
// 使用二分查找方法来寻找第一个错误的版本
static int FirstBadVersion1(int n, int bad)
{
// 初始化左边界为第一个版本号
int left = 1;
// 初始化右边界为最后一个版本号
int right = n;
// 当左边界小于右边界时进行循环
while (left < right)
{
// 计算中间版本号
int mid = left + (right - left) / 2;
// 如果中间版本号是错误的版本
if (IsBadVersion(mid))
{
// 将右边界移到中间版本号
right = mid;
}
else
{
// 如果中间版本号不是错误的版本，将左边界移到中间版本号的下一个版本
left = mid + 1;
}
}
// 返回左边界，即为第一个错误的版本
return left;
}
// 方法二：线性扫描
// 使用线性扫描方法来寻找第一个错误的版本
static int FirstBadVersion2(int n, int bad)
{
// 遍历所有版本号
for (int i = 1; i <= n; i++)
{
// 如果当前版本是错误的版本，返回该版本号
if (IsBadVersion(i))
{
return i;
}
}
// 如果没有找到错误的版本，返回-1
return -1; // Not reached, just to satisfy compiler
}
// 根据API判断版本是否错误
// 根据API判断给定版本号是否是错误的版本
static bool IsBadVersion(int version)
{
// 这是一个占位函数，实际实现取决于上下文
// 这是一个演示API使用方法的模拟函数
// 在真实情况下，此函数应调用API以确定版本是否错误
return version >= 4; // Change this condition based on actual implementation
}
#endregion
}
278.4 运行结果
示例1 方法1 输出：4
示例1 方法2 输出：4
示例2 方法1 输出：1
示例2 方法2 输出：-1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
