LeetCode算法题FirstBadVersion（Java实现三种解法）

这是悦乐书的第200次更新，第210篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第66题（顺位题号是278）。您是产品经理，目前领导团队开发新产品。不幸的是，您产品的最新版本未通过质量检查。由于每个版本都是基于以前的版本开发的，因此坏版本之后的所有版本也是坏的。

假设您有n个版本[1,2，...，n]并且您想找出第一个坏的版本，这会导致以下所有版本都不好。您将获得一个API bool isBadVersion（版本），它将返回版本是否错误。 实现一个函数来查找第一个坏版本。 您应该最小化对API的调用次数。

例如：

给定n = 5，版本= 4是第一个坏版本。

调用isBadVersion（3） - > false

调用isBadVersion（5） - > true

调用isBadVersion（4） - > true

然后4是第一个坏版本。

isBadVersion方法在父类VersionControl中定义。

boolean isBadVersion（int version）;

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

对于从1到n的所有版本中，假设好坏版本的临界是第mid个，那么从1到mid-1都是好版本，在调用isBadVersion方法时总是返回false;从mid到n都是坏版本，调用isBadVersion方法时返回的都是true。

直接使用for循环，指针从1开始，依次调用isBadVersion方法，如果返回true，则返回当前指针所表示的版本，反之返回n，即最后一个版本。

此解法的时间复杂度是O(n)，空间复杂度是O(1)，但是提交后提示超时了，我们需要一个更快的方法。

public int firstBadVersion(int n) {
    for (int i = 1; i 

public int firstBadVersion2(int n) {
    int left = 1;
    int right = n;
    while (left 

public int firstBadVersion3(int n) {
    if (n == 0) {
        return 0;
    }
    return helper(n, 1, n);
}

public int helper(int n, int start, int end) {
    if (start >= end) {
        return start;
    }
    int middle = start + (end - start)/2;
    if (isBadVersion(middle)) {
        return helper(n, start, middle);
    } else {
        return helper(n, middle + 1, end);
    }
}