来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-bad-version/
题目描述
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
题目分析
本题采用二分查找实现，因为题目要求『你应该尽量减少对调用 API 的次数』，尽量避免调用次数。
代码实现
public class DiYiGeCuoWuBanBen_278 {
public static int BAD_VERSION;
public static void main(String[] args) {
DiYiGeCuoWuBanBen_278 erFenChaZhao_704 = new DiYiGeCuoWuBanBen_278();
BAD_VERSION = 4;
erFenChaZhao_704.firstBadVersion(5);
}
private boolean isBadVersion(int version) {
if (version == BAD_VERSION) {
return true;
}
return false;
}
public int firstBadVersion(int n) {
int leftIndex = 1;
int rightIndex = n;
// 循环直到 左右端点相同
while (leftIndex < rightIndex) {
int midIndex = (rightIndex + leftIndex) / 2;
if (isBadVersion(midIndex)) {
rightIndex = midIndex;
} else {
leftIndex = midIndex + 1;
}
}
System.out.println(leftIndex);
return leftIndex;
}
}
运行结果：
复杂度
- 时间复杂度：O(logn)，其中 n 是定版本的数量。
- 空间复杂度：O(1)，只需要常数的空间保存变量。
好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！
